java实现二分查找

• 二分查找

　　找到数组的中间项，比较数key和中间树的大小，如果小于中间项，就查找前半部分，如果大于中间项，就查找后半部分。

• 非递归实现

public int BinarySearch（int[] a, int key）{
       int  beginIndex=0;
       int  endIndex=a.length-1;
       int midIndex=0;
       while(a!==null&&beginIndex<endIndex){
               midIndex=(beginIndex+endIndex)/2;
               if(midIndex==key) return midIndex;
               else if(midIndex<key) beginIndex=midIndex+1;
               else endIndex=midIndex-1;
           }  
        return -1;
}

• 递归实现

public int BinarySearch(int[] a , int key , int beginIndex, int endIndex){
        int midIndex=(beginIndex+endIndex)/2;
        if(a==null||beginIndex<endIndex||key<a[beginIndex]) return -1; 
        else if(a[midIndex]==key) return midIndex;
        else if(a[midIndex]>key) return BinarySearch(a,key,beginIndex,midIndex-1);
        else  return BinarySearch(a,key,midIndex+1,endIndex);
}