14. 二分查找

给定一个排序的整数数组（升序）和一个要查找的整数target，用O(logn)的时间查找到target第一次出现的下标（从0开始），如果target不存在于数组中，返回-1。

样例

在数组 [1, 2, 3, 3, 4, 5, 10] 中二分查找3，返回2。

给一个real耿直的解法

 1 int binarySearch(vector<int> &array, int target) {
 2         // write your code here
 3         int left=0,right=array.size()-1;
 4         int mid;
 5         while(left<=right){
 6             mid=left+(right-left)/2;
 7             if(target>array[mid]){
 8                 left=mid+1;
 9             }
10             else if(target<array[mid]){
11                 right=mid-1;
12             }
13             else{
14                 if(target==array[left]){
15                      return left;
16                 }
17                 else if(target==array[right]){
18                     return right;
19                 }
20                 else{
21                     while(array[mid-1]==array[mid]){
22                         mid--;
23                     }
24                     return mid;
25                 }
26                 
27             }
28         }
29         
30         return -1;
31     }

第一个else里面是处理几乎快找到解的时候（二分不下去了）会发生的各种情况

1、mid无法取到0或者最后

2、mid是对应target但是不是第一个出现的target