剑指offer37.数字在升序数组中出现的次数

解题&＃xff1a;
1 暴力
2 双指针
3 但是我们看到升序数组&＃xff0c;应该想到二分法

二分查找&＃xff1a;
target&＃61;k
1 查找第一个出现的k的位置
2 查找第一个大于k的值的位置

熟练上面两种搜索的做法&＃xff0c;要注意边界条件。

注意二分查找mid假如是left&＃61;right-1&＃xff0c;那mid总是偏向left&＃xff0c;因此用left去定位&＃xff0c;right不断往left靠就可以了。所以注意
left&＃61;mid&＃43;1;
right&＃61;mid;

class Solution {
public:int GetNumberOfK(vector<int> data ,int k) {int n&＃61;data.size();if(n&＃61;&＃61;0) return 0;//二分法//定义下界为第一个值&＃xff0c;上界为最后一个值后一个值int left&＃61;0,right&＃61;n;//right必须得是data.size(),考虑data全都小于k的情况//那么left&＃61;mid&＃43;1&＃xff0c;最终必然走到越界//寻找下界while(left<right){int mid&＃61;left&＃43;(right-left)/2;if(data[mid]<k)left&＃61;mid&＃43;1; elseright&＃61;mid;}int lbound&＃61;left;left&＃61;0,right&＃61;n;//寻找上界while(left<right){int mid&＃61;left&＃43;(right-left)/2;if(data[mid]<&＃61;k)left&＃61;mid&＃43;1;elseright&＃61;mid;}int rbound&＃61;left;return rbound-lbound;// //双指针
// int left&＃61;0,right&＃61;n-1;
// for(left;left
// if(data[left]&＃61;&＃61;k)
// break;
// }// for(right;right>&＃61;0;--right){
// if(data[right]&＃61;&＃61;k)
// break;
// }// return left<&＃61;right?right-left&＃43;1:0;}
};