剑指offer37：统计一个数字在排序数组中出现的次数

 1 class Solution {
 2 public: // 二分查找 O(log n)
 3     int GetNumberOfK(vector<int> data ,int k) {
 4         if (data.size() <=0)
 5             return 0;
 6         int count = 0;
 7         int begin = 0;
 8         int end = data.size()- 1;
 9 
10         while (begin<=end){
11             int mid = (begin + end) /2;
12             if (data[begin]==k && data[end] == k)
13                 break;
14 
15             // 缩小start和end的范围，使start指向第一个k，end指向最后一个k
16             if (data[begin] < k)
17                 ++begin;
18             if (data[end] > k)
19                 --end;
20 
21             if (data[mid]< k){
22                 end = mid -1;
23             } else if (data[mid] > k){
24                 begin = mid +1;
25             }
26         }
27         if (data[begin] ==k && data[end]==k)
28             return end - begin +1 ; // beg和end分别对应第一个和最后一个k所在位置
29         else
30             return 0;     // beg>end 不存在该元素
31 
32     }
33 };

 1 class Solution 
 2 {
 3 public:
 4     int GetNumberOfK(vector<int> data ,int k)
 5     {
 6         int s1 = lower_bound(data.begin(),data.end(),k)-data.begin();
 7         int s2 = upper_bound(data.begin(),data.end(),k)-data.begin();
 8         //cout<<s1<<" "<<s2<<endl;
 9         return s2-s1;
10     }
11 };