欢迎 fork and star:Nowcoder-Repository-github
34. Search for a Range
题目
- Given an array of integers sorted in ascending order,
- find the starting and ending position of a given target value.Your algorithm 's runtime complexity must be in the order of O(log n).
- If the target is not found in the array, return [-1, -1].
- For example,
- Given [5, 7, 7, 8, 8, 10] and target value 8,
- return [3, 4].'
解析
关于二分法的查找延伸的问题, 细节要注意
注意使用 stl 的函数实现, 在 [first,last) 区间查找
- class Solution_34 {
- public:
- int findUpBound(vector<int>& nums, int target) // 找上边界
- {
- int low = 0, high = nums.size() - 1;
- if (nums.back()<target)
- {
- return -1;
- }
- while (low<=high)
- {
- int mid = (low + high) >> 1;
- if (nums[mid]<=target) /// 向右夹逼, 找到右边界
- {
- low = mid + 1;
- }
- else
- {
- high = mid - 1;
- }
- }
- return high; // 向右夹逼, 返回 high
- }
- int findDownBound(vector<int>& nums, int target) // 找下边界
- {
- int low = 0, high = nums.size() - 1;
- if (nums.front()>target)
- {
- return -1;
- }
- while (low<=high)
- {
- int mid = (low + high) >> 1;
- if (nums[mid]<target) /// 向左夹逼, 则找到左边界
- {
- low = mid + 1;
- }
- else
- {
- high = mid - 1;
- }
- }
- return low; // 向左夹逼, 返回 low
- }
- vector<int> searchRange(vector<int>& nums, int target) { // 找到 target 的上下边界
- vector<int> vec(2, -1);
- if (nums.size() == 0 || nums.front()>target || nums.back()<target)
- {
- return vec;
- }
- int high = findUpBound(nums, target);
- int low = findDownBound(nums, target);
- if ((low == high&&nums[low] == target) || (low<high))
- {
- vec[0] = low;
- vec[1] = high;
- }
- return vec;
- }
- vector<int> searchRange2(int A[], int n, int target) {
- vector<int > vec(A,A+n); // 初始化
- return searchRange1(vec, target);
- }
- vector<int> searchRange1(vector<int>& nums, int target) { // 找到 target 的自身上下边界, 非严格上下界
- vector<int> vec(2, -1);
- if (nums.size() == 0||nums.front()>target||nums.back()<target)
- {
- return vec;
- }
- //pair<int, int> temp;
- // 针对 upper_bound the objects in the range [first,last) are accessed. 本身传入的迭代器 end(). 就是指向下一个位置
- auto range=equal_range(nums.begin(), nums.end(), target); // 返回的是两个迭代器, 解引用得到值
- if (*range.first!=target||*(range.second-1)!=target)
- {
- return vec;
- }
- vec[0]=(range.first-nums.begin()); //stl: distance()计算迭代器之间的距离
- vec[1]=(range.second - nums.begin()-1);
- return vec;
- }
- };
题目来源
- 34. Search for a Range
- 34. Search for a Range
来源: http://www.bubuko.com/infodetail-2482491.html