这个题我的思路是从开始遍历数组，找到一样的数字+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 }
原文：https://www.cnblogs.com/neverland0718/p/11181531.html