LeetCode 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].

---

本题要在一个有序数组中求一个数出现的下标区间，如果该数不在数组中，返回[-1,-1]，要求用O(lgn)时间复杂度。 很明显用两次二分搜索找到该数的上下区间即可，可以认为是二分搜索的综合题。下界就是第一个不小于target的位置，所以当找到中间值和target相等时，我们要继续往左找。上界就是最后一个不大于target的位置，所以当找到中间值和target相等时，我们要继续往右找。理清了这个思路之后就很好写代码了，如下： [cpp] class Solution { private: int lowerbound(vector<int>& nums, int target) { int l = 0, r = nums.size() – 1; while (l <= r) { int m = l + (r – l) / 2; if (nums[m] < target)l = m + 1; else if (nums[m] >= target)r = m – 1; } return l; } int upperbound(vector<int>& nums, int target) { int l = 0, r = nums.size() – 1; while (l <= r) { int m = l + (r – l) / 2; if (nums[m] <= target)l = m + 1; else if (nums[m] > target)r = m – 1; } return r; } public: vector<int> searchRange(vector<int>& nums, int target) { int lower = lowerbound(nums, target), upper = upperbound(nums, target); if (lower <= upper)return vector<int>({ lower, upper }); else return vector<int>({ -1,-1 }); } }; [/cpp] 本代码提交AC，用时9MS。 注意一点，为啥lowerbound是返回l，而upperbound是返回r呢，对于lowerbound，我们想象一下当中值等于target时，我们不停的往左走，即r=m-1，直到l<=r不再满足，即此时r已经小于l了，也就是说r往左走过头了，使得r对应的值已经小于target了，但此时l对应的值还是等于target，所以根据lowerbound的定义，我们返回l。对于uppperbound也类似，当中值等于target时，不停往右走，即l=m+1，直到不满足l<=r，此时l对应的值已经大于target，而r对应的值还是等于target的，根据upperbound的定义，我们返回r。 其实，STL中已经实现了lower_bound和upper_bound，其lower_bound和上文的lowerbound含义是一致的，upper_bound稍有不同，STL中的upper_bound是返回第一个大于target的位置，比上文的upperbound要大一个位置。所以如果借助STL的算法，需要对upper_bound返回的位置减1。代码如下： [cpp] class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { if (nums.size() == 0)return vector<int>({ -1,-1 }); vector<int>::iterator lower = lower_bound(nums.begin(), nums.end(), target), upper = upper_bound(nums.begin(), nums.end(), target) – 1; if (lower <= upper)return vector<int>({ lower – nums.begin(), upper – nums.begin() }); else return vector<int>({ -1,-1 }); } }; [/cpp] 本代码提交AC，用时16MS。貌似STL中的实现也是O(lgn)的，看来性能还是有所差别。]]>