Binary Search (二分查找)

思路就是砍一半, 适用于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 }