剑指offer——56在排序数组中查找数字

题目描述

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

题解：

　　使用二分法找到数k然后向前找到第一个k，向后找到最后一个k，即可知道有几个k了

　　但一旦n个数都是k时，这个方法跟从头遍历没区别，都是O(N)的复杂度

　　可以再次利用二分法，在第一次找到k的左半部分使用二分法找到不再出现k的位置，其右半部份类似。

 1 class Solution01 {
 2 public:
 3     int GetNumberOfK(vector<int> data, int k) {
 4         if (data.size() == 0)return 0;
 5         int L = 0, R = data.size() - 1, M;
 6         while (L <= R)
 7         {
 8             M = (R - L) / 2 + L;
 9             if (data[M] == k)break;
10             else if (data[M] > k)R = M - 1;
11             else L = M + 1;
12         }
13         if (L > R)return 0;
14         L = R = M;
15         int res = 0;
16         while (L >= 0 && data[L] == k) {
17             res++; --L;
18         }
19         while (R<data.size() && data[R] == k) {
20             res++; ++R;
21         }
22         return res - 1;
23     }
24 };
25 
26 class Solution02 {
27 public:
28     int GetNumberOfK(vector<int> data, int k) {
29         if (data.size() == 0)return 0;
30         int pM = find(data, 0, data.size() - 1, k);
31         if (data[pM] != k)return 0;
32         int pL = pM, pR = pM;
33         while (pL !=-1 && data[pL] == k) pL = find(data, 0, pL - 1, k);
34         while (pR != -1 && data[pR] == k) pR = find(data, pR + 1, data.size() - 1, k);
35         return (pR == -1 ? data.size() : pR) - pL - 1;
36     }
37     int find(const vector<int>data, int L, int R, const int k)
38     {
39         int M = -1;
40         while (L >= 0 && R < data.size() && L <= R)
41         {
42             M = (R - L) / 2 + L;
43             if (data[M] == k)break;
44             else if (data[M] > k)R = M - 1;
45             else L = M + 1;
46         }
47         return M;
48     }
49 };