思路就是砍一半, 适用于sorted array. 时间复杂度O(lgn).
每次都是取中间的跟target比较, 比target小的话目标值肯定在lower和mid之间, 比target大的话在mid和high之间~
1 public int binarySearch(int num[], int target){ 2 int lower = 0; 3 int high = num.length - 1; 4 while(lower <= high){ 5 int mid = lower + (high - lower) / 2; 6 if(num[mid] < target){ 7 lower = mid + 1; 8 }else if(num[mid] > target) 9 high = mid - 1; 10 else 11 return mid; 12 } 13 return lower; 14 }
原文：http://www.cnblogs.com/sherry900105/p/4293739.html