剑指offer系列30：数字在排序数组中出现的次数

这个题我的思路是从开始遍历数组，找到一样的数字+1，遍历完整个数组即可。我好想每次想到的都是普通的算法，o(╥﹏╥)o剑指offer上说既然是排序，自然就想到了用二分法做，我emmmmm……这个题用二分法做的话，如果发现中间这个k，还要去找它的前几个k和后几个k，就是说找到它的第一个k和最后一个k，等于还是要去遍历数组。因此由此可以想到用二分法的思路去寻找第一个k和最后一个k，有了这个思路，代码就很好写了。

在这里我说两点。首先是在求中值得时候，有两种办法，第一是（end - start）/2，第二种是（end + start）/2，其实第一种是计算两者之间的差的一半，而第二种是计算两者之间中间的坐标。这个算中间值的我经常弄混。还有就是二分法是个典型的递归结构，而在写递归结构的时候，往往要调用之前的函数，最好在中间做好递归的变量的控制，最后在返回递归函数，这是一种简单又思路清晰的写法。例如这个题的写法就是如此。

 1 #include<iostream>
 2 #include <vector>
 3 using namespace std;
 4 class Solution {
 5 public:
 6     int findfirstk(vector<int> data, int k, int start, int end)//寻找第一个k
 7     {
 8         if (start > end)//这个一定要写，因为有可能数组中没有这个数字
 9             return -1;
10         int mid = (end +start) >> 1;
11         int middata = data[mid];
12         if (middata == k)
13         {
14             if ((mid > 0 && data[mid - 1] != k)//找到第一个k
15                 || mid == 0)
16             {
17                 return mid;//递归终结条件
18             }
19             else
20             {
21                 end = mid - 1;
22             }
23         }
24         else
25         {
26             if (middata > k)
27                 end =mid-1;
28             else
29             {
30                 start =mid + 1;
31             }
32         }
33         return findfirstk(data, k, start, end);
34     }
35     int findlastk(vector<int> data, int k, int start, int end)//寻找最后一个k
36     {
37         if (start > end)
38             return -1;
39         int mid = (end + start) >> 1;
40         int middata = data[mid];
41         if (middata == k)//寻找第一个k，或者最后一个k
42         {
43             if (end== start)
44                 return end;
45             if (mid < end && data[mid + 1] != k)//找到第一个k
46             {
47                 return mid;//递归终结条件
48             }
49             else
50             {
51                 start =mid + 1;
52             }
53         }
54         else
55         {
56             if (middata > k)
57                 end = mid - 1;
58             else
59             {
60                 start = mid + 1;
61             }
62         }
63         return findlastk(data, k, start, end);
64     }
65     int GetNumberOfK(vector<int> data, int k)
66     {
67         int len = data.size();
68         if (len <= 0)
69             return 0;
70         int start = 0, end = len - 1,num=0;
71         int first = findfirstk(data, k, start, end);
72         cout << "first:" << first <<endl;
73         int last =findlastk (data, k, start, end);
74         cout << "last:" << last << endl;
75         if (first > -1 && last > -1)
76         {
77             num = last - first + 1;
78         }
79         return num;
80     }
81 
82 };
83 int main()
84 {
85     Solution so;
86     vector<int> test = { 1,2,3,3,3,3,4,5 };
87     cout << so.GetNumberOfK(test, 3) << endl;
88     return 0;
89 }