正文
【剑指offer】数字在排序数组中出现的次数，C++实现
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
原创博文，转载请注明出处！
# 题目
# 思路
利用二分查找法，查找元素k在排序数组中第一次出现的位置m及最后一次出现的位置n，m-n+1即为元素k再排序数组中出现的次数。
二分查找法在数组中找到第一个k的思路： 先拿数组中间元素mid和查找元素k比较，如果k<mid，则第一个k只可能出现在数组的前半段；如果k>mid，则第一个k只可能出现在数组的后半段；如果k=mid，则先判断中间元素是不是第一个k（如果mid前的元素不是k，则中间元素是第一个k；如果mid前的元素是k，则第一个k出现在数组的前半段。
二分查找法在数组中找到最后一个k的思路： 先拿数组中间元素mid和查找元素k比较，如果k<mid，则最后一个元素k只可能出现在数组的前半段；如果k>mid，则最后一个元素k只可能出现在数组的后半段；如果k=mid，则先判断中间元素是不是最后一个k（如果mid后的元素不是k，则中间元素是最后一个k；如果mid后的元素是k，则最后一个k出现在数组的后半段。
# 代码
1 #include <iostream>
2 #include <vector>
3 using namespace std;
4
5 class Solution {
6 public:
7 // 查找元素k在有序数组中出现的次数
8 int GetNumberOfK(vector<int> data ,int k)
9 {
10 // 特殊输入
11 if(data.size() == 0)
12 return 0;
13 cout<<data.size()<<endl;
14
15 // 在有序数组中查找k第一次出现的位置
16 int first = GetFirstK(data,k,0,data.size()-1);
17 cout<<first<<endl;
18
19 // 在有序数组中查找k最后一次出现的位置
20 int last = GetLastK(data,k,0,data.size()-1);
21 cout<<last<<endl;
22
23 // 计算次数
24 if(first != -1 && last != -1)
25 return last-first+1;
26
27 // 未找到元素
28 return 0;
29 }
30
31 // 二分查找法，查找第一个k的位置
32 int GetFirstK(vector<int> data,int k,int l,int r)
33 {
34 // 递归出口
35 if(l>r)
36 return -1;
37
38 int mid = (l+r)>>1;
39
40 if(k<data[mid])
41 {
42 r = mid-1;
43 }
44 else if (k>data[mid])
45 {
46 l = mid+1;
47 }
48 else
49 {
50 if((mid>0 && data[mid-1] != k) || mid == 0)
51 return mid;
52 else
53 r = mid-1;
54 }
55 return GetFirstK(data,k,l,r);
56 }
57
58 // 二分查找法，查找最后一个k的位置
59 int GetLastK(vector<int> data,int k,int l,int r)
60 {
61 if(l>r)
62 return -1;
63
64 int mid = (l+r)>>1;
65
66 if(k<data[mid])
67 r = mid-1;
68 else if(k>data[mid])
69 l = mid+1;
70 else
71 {
72 if((mid < data.size()-1 && data[mid+1]!=k) || mid == data.size()-1)
73 return mid;
74 else
75 l = mid+1;
76 }
77 return GetLastK(data,k,l,r);
78 }
79 };
80 int main()
81 {
82 cout << "二分查找法计算数字k在排序数组中出现的次数" << endl;
83 // 空数组
84 vector<int> arr1;
85 // 数组中不包含查找的数字
86 vector<int> arr2 = {1,3,5,7,9,10};
87 // 数组中包含查找的数组（出现一次）
88 vector<int> arr3 = {1,2,2,2,2,3,3,3,4,5};
89 // 数组中包含查找的数组（出现多次）
90 vector<int> arr4 = {1,2,3,4,4,4,7,8,9,10};
91 Solution solution;
92 cout<<solution.GetNumberOfK(arr1,4)<<endl;
93
94 return 10086;
95 }
96
