34. Search for a Range

题目：Search for a Range

原题介绍

原题链接：https://leetcode.com/problems/search-for-a-range/?tab=Description 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].

给出一组升序排好的数组，找到制定元素的起始和结束位置。要求时间复杂度O(log n)。 如果不存在则返回 [-1, -1]. 例： 在[5, 7, 7, 8, 8, 10] 中查找 8 结果是[3, 4]，及元素8的下标范围是3-4

思路

实质上就是查指定元素的下标下界和上界。在C++里面有对应的lower_bound和upper_bound函数可以直接调用，我们可以自己实现简单的二分查找来找到下界，然后上界只需要通过查找比target大1的元素对应的位置再减一就可以了。

参考代码

class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { vector<int> ans(2, -1); int len = nums.size(); if(!len) return ans; int left = lowerBound(nums, target); if(left < len && nums[left] == target) { ans[0] = left; ans[1] = lowerBound(nums, target + 1) - 1; } return ans; } private: // 找到第一个不小于目标元素对应的下标 int lowerBound(vector<int>& nums, int target) { int len = nums.size(); int i = 0, j = len, mid; while(i < j) { mid = i + (j - i) / 2; if(nums[mid] < target) i = mid + 1; else j = mid; } return i; } };