剑指 Offer 53 - I. 在排序数组中查找数字 I(LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置)——二分
题目链接:
- https://leetcode.cn/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof/
- https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
题目:
统计一个数字在排序数组中出现的次数。
解法:
两次二分,分别找左右边界,时间O(logN),空间O(1)
本题二分关键是,弄清二分结束后左右下标的位置。
左边界:如下代码用于寻找左边界
while(l<=r) {
int mid = (l+r)>>1;
if(nums[mid] >= target) {
r = mid - 1;
} else {
l = mid + 1;
}
}
上述循环结束后,左右指针指向如下图所示
右边界:如下代码用于寻找右边界
while(l<=r) {
int mid = (l+r)>>1;
if(nums[mid] <= target) {
l = mid + 1;
} else {
r = mid - 1;
}
}
上述循环结束后,左右指针指向如下图所示
代码:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size()-1;
while(l<=r) {
int mid = (l+r)>>1;
if(nums[mid] >= target) {
r = mid - 1;
} else {
l = mid + 1;
}
}
int lower_bound = l;
// cout << "l = " << l;
l = 0, r = nums.size() - 1;
while(l<=r) {
int mid = (l+r)>>1;
if(nums[mid] <= target) {
l = mid + 1;
} else {
r = mid - 1;
}
}
int upper_bound = r;
// cout << ", r = " << r << endl;
return upper_bound - lower_bound + 1;
}
};
int main()
{
Solution slu;
vector<int> v1 = {5,7,7,8,8,10};
vector<int> v2 = {5,7,7,8,8,10};
vector<int> v3 = {1};
int t1 = 8, t2 = 6, t3 = 1;
cout << slu.search(v1, t1) << endl;
cout << slu.search(v2, t2) << endl;
cout << slu.search(v3, t3) << endl;
return 0;
}