53-I. 在排序数组中查找数字 I
1. 描述
统计一个数字在排序数组中出现的次数。
2. 例子
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
3. 限制
- 0 <= 数组长度 <= 50000
4. 题解
n = i_nums.size()
时间复杂度: O($log_2n$)
空间复杂度: O(1)
class Solution
{
private:
int search(vector<int> &i_nums, int target, int left, int right, bool isFindLeft)
{
int middle;
while(left <= right)
{
middle = left + ((right - left) >> 1);
if(i_nums[middle] == target &&
(isFindLeft && (middle == 0 || i_nums[middle - 1] != target)
|| !isFindLeft && (middle == i_nums.size() - 1 || i_nums[middle + 1] != target))
)
break;
else if(isFindLeft && i_nums[middle] < target || !isFindLeft && i_nums[middle] <= target)
left = middle + 1;
else
right = middle - 1;
}
return middle;
}
public:
// int search(vector<int>& nums, int target)
int search(vector<int> &i_nums, int target)
{
if(i_nums.empty()) return 0;
int leftBorder = search(i_nums, target, 0, i_nums.size() - 1, true);
if(i_nums[leftBorder] != target) return 0;
int rightBorder = search(i_nums, target, leftBorder, i_nums.size() - 1, false);
return rightBorder - leftBorder + 1;
}
};