1 定义
折半查找算法也称二分查找算法或折半搜索算法，是一种在有序数组（即前提必须是数组是已经排好序的）中查找某一特定元素的搜索算法。搜素过程是
1）计算中间元素mid
从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；
2）比较左边元素left, 比较右边元素right
如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。
这种搜索算法每一次比较都使搜索范围缩小一半。如下图，lowerBound代表查找起始范围，upperBound代表查找终止位置，mid是中间元素。我们需要考虑的是算法何时结束？
2 java代码实现
我们定义如下的一个函数来实现二分查找
/ * @param a 待查找的数组
* @param fromIndex 查找的起始位置
* @param toIndex 查找的终止位置是（toIndex-1）
* @param key 要查找的数据
* @return 查找数据在数组中的位置
* 如果查找的数据不存在，则返回 - 1
* insertion point是查找数据如果插入数组时它插入的位置
*/
public static int search(int[] a,int fromIndex,int toIndex,int key){
//add your code here
}
1) 代码第一次实现如下
观察上述代码，你能发现几个问题呢？
1）输入控制
如果数组为null，那么a[i]势必会抛出异常；
如果输入的fromIndex>toIndex，函数本身就没有意义；而且fromIndex和toIndex如果不在数组长度范围(0~length-1)内怎么办?
上述可能出现的异常，都源于没有对输入参数做控制处理。
//input control
if(a==null) //if a is null
return -1;
if(fromIndex<0 || toIndex>a.length-1 || fromIndex>toIndex)
throw new Exception("illegal input!");
2）注意到while循环里面mid没有？在key<a[mid]和key>a[mid]之前，a[mid]已和key比较过，能进行key<a[mid]或key>a[mid]，说明a[mid]肯定是和key不相等,所以后面没有必要再比较mid了，修改如下
3）注意到while循环没有循环结束的条件，这是致命的。那么什么时候二分查找结束呢？
注意到进入下一次二分查找改变的地方是upperBound=mid-1和lowerBound=mid+1,所以在这里我们考虑临界条件发生的情况。如果二分后还有2个元素时，我们记为i,i+1,那么mid=(2i+1)/2=i，那么分为2半（i,upperBound=mid-1=i-1）(lowerBound=mid+1=i+1,i+1)
如果是（i,upperBound=mid-1=i-1），那么再做一次划分就会出现lowerBound>upperBound的异常；
如果是(lowerBound=mid+1=i+1,i+1)，那么再做一次划分也会出现lowerBound>upperBound；
所以循环结束的条件是数组中只剩2个元素时，直接折半查找每次把查找范围砍掉一半，最后当只有一个元素时（此时lowerBound=upperBound），经过语句upperBound=mid-1或lowerBound=mid+1后，lowerBound>upperBound，此时循环结束。所以临界条件（base
case）是lowerBound>upperBound，此时停止查找。
package zyang.binaryInsertSort;
/**
* @version 1.0
* @date 2012-11-14 上午10:03:59
* @fuction binary search
* binary search
* 折半搜索，也称二分查找算法、二分搜索，是一种在有序数组中查找某一特定元素的搜索算法。
* 搜素过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜素过程结束；
* 如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
* 如果在某一步骤查找的数组的下界大于上届，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。
* 时间复杂度：二分搜索每次把搜索区域砍掉一半，很明显时间复杂度为O(logn)。（n代表集合中元素的个数）
* 空间复杂度：O(1)
*/
public class BinarySearch
{
private BinarySearch()
{}
/**
* 根据给定数组下标的范围,用折半查找算法查找指定数据
* 数组必须是已排好序的，否则查找结果没有意义。如果数组中有相等的元素，则会找到其中之一，至于是哪一个，是不确定的
* @param a 待查找的数组
* @param fromIndex 查找的起始位置
* @param toIndex 查找的终止位置
* @param key 要查找的数据
* @return 查找数据在数组中的位置
* 如果查找的数据不存在，则返回(- 1)
* insertion point是查找数据如果插入数组时它插入的位置
* @throws Exception
*/
//implement by loop
public static int search(int[] a,int fromIndex,int toIndex,int key) throws Exception
{
/*
* input control:specail case
* 1)a is null
* 2)[fromIndex,toIndex]not in range [0, a.length-1]
* 3) fromIndex>toIndex
* step:
* 1) get mid
* 2) compare key with mid
* just equal:key==mid,return mid
* in left:key<mid, toIndex=mid-1
* in right:key>mid, fromIndex=mid+1
* 3) do the loop of step2
* base case: fromIndex > toIndex
*/
//input control
if(a==null) //if a is null
return -1;
if(fromIndex>toIndex || fromIndex<0 || toIndex>a.length-1)
throw new Exception("illegal input!");
int mid; //mid
while(fromIndex <= toIndex){ //base case:lowerBound>upperBound
mid =(fromIndex+toIndex)/2;
//found it
if(key==a[mid])
return mid;
//left
if(key<a[mid])
toIndex=mid-1;
//right
else
fromIndex=mid+1;
}//end while
return -1; //not found
}//end search()
//implement by recursion
public static int searchRecursion(int[] a,int fromIndex, int toIndex, int key) throws Exception{
//input control
if(a==null) //if a is null
return -1;
if(fromIndex>toIndex || fromIndex<0 || toIndex>a.length-1)
throw new Exception("illegal input!");
int mid; //mid
//base case
if(fromIndex>toIndex)
return -1; //not found
else{
mid=(fromIndex+toIndex)/2;
if(key==a[mid])
return mid;
if(key<a[mid]) //left
searchRecursion(a, fromIndex, mid-1, key);
else
searchRecursion(a, mid+1, toIndex, key);
}//end else
}//end searchRecursion()
public static int search(int[] a,int key) throws Exception
{
return search(a, 0, a.length-1, key);
}
/**
* @param args
* @throws Exception
*/
public static void main(String[] args) throws Exception {
//test case
int[] a={1,2,3,4,5,6}; //test array
//specail input
//a==null
System.out.println("a==null");
System.out.println(BinarySearch.search(null,2,5,4));
//fromIndex>toIndex
System.out.println("fromIndex>toIndex");
System.out.println(BinarySearch.search(a,5,2,4));
// out of array bound:fromIndex<0 toIndex<0 toIndex>a.length-1
System.out.println("out of array bound");
System.out.println(BinarySearch.search(a,-1,2,4));
System.out.println(BinarySearch.search(a,1,-2,4));
System.out.println(BinarySearch.search(a,1,7,4));
//logic test
System.out.println("key in the arrary:"+BinarySearch.search(a, 4));
System.out.println("key not in the array:"+BinarySearch.search(a, 4));
char[] test={'2','3'};
}
}
折半查找的边界条件
折半查找每次把查找范围砍掉一半，最后当只有一个元素时（此时lowerBound=upperBound），经过语句upperBound=mid-1或lowerBound=mid+1后，lowerBound>upperBound，此时循环结束。所以临界条件（base case）是lowerBound>upperBound，此时停止查找。
3 复杂度分析
折半查找每次把搜索区域砍掉一半，很明显时间复杂度为
。（n代表集合中元素的个数）
