题目描述
二分 算法基础课模板题
算法1
(时间复杂度) $O(logn)$
C++ 代码
class Solution {
public:
int getNumberOfK(vector<int>& nums , int k) {
int l1 = 0 , r1 = nums.size() - 1;
int x = k;
if(r1 < 0)return 0;
while(l1 < r1)
{
int mid = l1+r1 >>1;
if(nums[mid] >= x) r1 = mid;
else l1 = mid +1;
}
int l2 = 0,r2 = nums.size() - 1;
while(l2 < r2)
{
int mid = l2 + r2 +1 >>1;
if(nums[mid] <= x) l2 = mid;
else r2= mid - 1;
}
if(nums[l2] != k&& nums[l1] != k)return 0;
return l2 -l1+1;
}
};