[LeetCode] Search for a Range

Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order ofO(logn).

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(logn)。3次二分查找。第一次找到一个值为target的下标k，，第二次找到0~k中值为target的最小下标，第三次找到k~len-1中值为target的最大下标。每次的时间复杂度为O（logn）。

class Solution {public:vector<int> searchRange(vector<int>& nums, int target) {vector<int> result({-1, -1});int start=0, end=nums.size()-1;int middle;//找到第一个while(start<=end){middle=(start+end)/2;if(nums[middle]==target){result[0]=result[1]=middle;break;}else if(nums[middle]>target){end=middle-1;}else{start=middle+1;}}if(result[0]!=-1){//找到最小的那个下标start=0;end=result[0]-1;while(start<=end){middle=(start+end)/2;if(nums[middle]==target){end=middle-1;result[0]=middle;}else{start=middle+1;}}//找到最大的那个下标start=result[1]+1;end=nums.size()-1;while(start<=end){middle=(start+end)/2;if(nums[middle]==target){start=middle+1;result[1]=middle;}else{end=middle-1;}}}return result;}};

你爱我吗？已经爱到危险的程度了.危险到什么程度？已经不能一个人生活。