剑指Offer——数字在排序数组中出现的次数

 1 class Solution {
 2 public:
 3     int GetNumberOfK(vector<int> data, int k) {
 4         int dataSize = data.size();
 5         if(dataSize == 0) return 0;
 6         int firstK = GetPositionOfFirstK(data, k, 0, dataSize - 1);
 7         if(firstK == -1) return 0;  // k不存在
 8         int lastK = GetPositionOfLastK(data, k, 0, dataSize - 1);
 9         return lastK - firstK + 1;
10     }
11     int GetPositionOfFirstK(vector<int> data, int k, int left, int right) { // 二分找最左的k的位置
12         int mid = (left + right) >> 1;
13         while(left < right) {
14             if(data[mid] > k) {
15                 right = mid - 1;
16             } else if(data[mid] < k) {
17                 left = mid + 1;
18             } else {
19                 if(data[left] != k) left++;
20                 else return left;
21                 right = mid;
22             }
23             mid = (left + right) >> 1;
24         }
25         return data[mid] == k ? mid : -1;
26     }
27     int GetPositionOfLastK(vector<int> data, int k, int left, int right) {  // 二分找最右的k的位置
28         int mid = (left + right) >> 1;
29         while(left < right) {
30             if(data[mid] < k) {
31                 left = mid + 1;
32             } else if(data[mid] > k) {
33                 right = mid - 1;
34             } else {
35                 if(data[right] != k) right--;
36                 else return right;
37                 left = mid;
38             }
39             mid = (left + right) >> 1;
40         }
41         return data[mid] == k ? mid : -1;
42     }
43 };