折半查找法也称为二分查找法，它充分利用了元素间的次序关系，采用分治策略。基本思想是，将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止。如 果x<a[n/2]，则我们只要在数组a的左半部继续搜索x（这里假设数组元素呈升序排列）。如果x>a[n/2]，则我们只要在数组a的右半部继续搜索x。每找一次目标范围就缩小一半，缺点是：集合中元素必须是有序的，升序降序都行。
?
折半查找法：
在有序按照升序排列的表中，把待查找数据值与查找范围的中间元素值进行比较，会有三种情况出现：
1、待查找数据值与中间元素值正好相等，则返回中间元素值的索引。
2、待查找数据值比中间元素值小，则以整个查找范围的前半部分作为新的查找范围，执行1），
? ? ? ? ? ? ? 直到找到相等的值。
3、待查找数据值比中间元素值大，则以整个查找范围的后半部分作为新的查找范围，执行1），
? ? ? ? ? ? ?直到找到相等的值。
4、如果最后找不到相等的值，则返回错误提示信息。
? ? ??按照二叉树来理解：中间值为二叉树的根，前半部分为左子树，后半部分为右子树。
? ? ??折半查找法的查找次数正好为该值所在的层数。等概率情况下，约为log2(n+1)-1
?
代码示例：
方案一、非递归查找
/**
* 假设升序排列
* @param srcArray ?集合
* @param des ?待查找元素
* @return 也许能找到,也许找不到,返回位置
*/
public static int binarySearch(Integer[] srcArray, int des) {
? ?int low = 0; ? ? ? ? ? ? ? ? ? ? //第一个元素下标为0
? ?int high = srcArray.length - 1; //最后一元素位置下标为长度减1
?
? ?while ((low <= high) && (low <= srcArray.length - 1)
? ? ? ? ? ?&& (high <= srcArray.length - 1)) {
? ?
? ? //左移一位,相当于除以2,得到最中间的元素
? ? ? ?int middle = (high + low) >> 1;
? ? ? ? ? ?
? ? ? ?if (des == srcArray[middle]) {
? ? ? ? //中间元素刚好等于待查找元素
? ? ? ? ? ?return middle;
? ? ? ?} else if (des < srcArray[middle]) {
? ? ? ? //因为升序排列,中间元素大于待查找元素,因因此待查找元素如果存在,只会落在左半边元素中
? ? ? ? ? ?high = middle - 1;
? ? ? ?} else {
? ? ? ? //因为升序排列,中间元素小于待查找元素,因因此待查找元素如果存在,只会落在右半边元素中
? ? ? ? ? ?low = middle + 1;
? ? ? ?}
? ?}
? ?return -1;
}
?
?
方案二、递归查找
// 递归法(升序排列的集合)
int IterBiSearch(int data[], int target, int begin, int last) {
int mid = (begin + last) / 2;
if (target == data[mid]) {
return mid;
} else if (target < data[mid]) {
return IterBiSearch(data, target, begin, mid - 1);
} else if (target > data[mid]) {
return IterBiSearch(data, target, mid + 1, last);
}
return -1;
}
原文：http://gaojingsong.iteye.com/blog/2284790