【剑指offer】数字在排序数组中出现的次数

题意：统计一个数字在排序数组中出现的次数。

题解：最容易想到的就是暴力统计。O(n)。但是这题是有序数组，暗示我们可以用二分优化到O(logn)。

第一次二分k最先出现的位置，第二次二分k最后出现的位置，即

data[mid-1] == k, 此时最先出现的k就应该往前找。

data[mid+1] == k, 此时最后出现的k就应该往后找。

代码：

 1 class Solution {
 2 public:
 3     int GetNumberOfK(vector<int> data ,int k) {
 4         /*
 5         int len = data.size();
 6         int cnt = 0;
 7         for(int i = 0; i < len ;i++){
 8             if(data[i] == k){
 9                 cnt++;
10             }
11         }
12         return cnt;  */
13         int first = BinSearch1(data,k);
14         int last = BinSearch2(data,k);
15         if(first == -1 || last == -1)    return 0;
16         else    return (last - first + 1);
17     }
18 private:
19     int BinSearch1(vector<int> data, int k){
20         int low = 0; int high = data.size()-1;
21         while(low <= high){
22             int mid = (low+high)/2;
23             if(data[mid] < k)    low = mid + 1;
24             else if(data[mid] > k)    high = mid - 1;
25             else {
26                 if((data[mid-1] == k) && (mid-1 >= 0)){
27                     high = mid-1;
28                 }
29                 else    return mid; 
30            }
31         }
32         return -1;
33     }
34     int BinSearch2(vector<int> data, int k){
35         int low = 0; int high = data.size() - 1;
36         while(low <= high){
37             int mid = (low+high)/2;
38             if(data[mid] < k)    low = mid + 1;
39             else if(data[mid] > k)    high = mid - 1;
40             else{ 
41                 if((data[mid+1] == k) && (mid+1 < data.size())){
42                     low = mid + 1;
43                 }
44                 else    return mid;
45             }
46         }
47         return -1;
48     }
49 };

好久没写代码。。二分居然一下子写错了。。debug好久。。绝望。:(