学步园

二分查找算法针对的是已经排好序的数组，下面以升序排列的数组来实现查找。 

package algorithm.search;   
/**  
* 二分查找算法  
*   
* */  
public final class BinarySearch {   
  
public static int find(int[] a, int key) {   
   return find(a, 0, a.length - 1, key);   
}   
  
// 非递归实现   
public static int find(int[] a, int fromIndex, int toIndex, int key) {   
   int low = fromIndex;   
   int high = toIndex;   
  
   while (low <= high) {   
    // 无符号右移位逻辑运算   
    int mid = (low + high) >>> 1;   
    int midVal = a[mid];   
  
    if (midVal < key)   
     low = mid + 1;   
    else if (midVal > key)   
     high = mid - 1;   
    else  
     return mid; // key found   
   }   
   return -(low + 1); // key not found.   
}   
  
// 递归实现   
public static int search(int[] a, int fromIndex, int toIndex, int key) {   
   if(fromIndex > toIndex) {   
    return -1;   
   }   
   int mid = (fromIndex + toIndex) >>> 1;   
   if(a[mid] < key) {   
    return search(a, mid + 1, toIndex, key);   
   } else if(a[mid] > key) {   
    return search(a, fromIndex, mid - 1, key);   
   } else {   
    return mid;   
   }   
}