Searchforarange寻找上下界-Leetcode

原题如下：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 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)的复杂度了。

后来在别人的答案里看到一个非常巧妙的实现，利用了二分法的一点变化。传统的二分法采用如下结构：

1intleft=0;2intright=length-1;3intmiddle=(left+right)/2;4while(left<right){5if(middle>target){6right=middle-1;7}8elseif(middle>target){9left=middle+1;10}11else{12returnmiddle;13}14}15returnleft;

在这个题目中，我们不是要找到一个特定的元素，而是要找到这样一组元素的上下界。那就要对二分法进行修改。

不再是找到相等元素就跳出循环，而是找到相等元素就继续把边界向另一端推进，直到推进到相等元素的最后一个为止。

这样一来，我们只需运行两次方向不同的二分就可以找到上下界了。

代码如下：

1publicclassSolution {2publicint[] searchRange(int[] nums,inttarget) {3intleft=0,right=nums.length;//注意 右边界不是取的nums.length-1。这是为了方便做第29行的判断.4intmid=(left+right)/2;5while(left<right){6if(nums[mid]>=target){7right=mid;8}9else{10left=mid+1;11}12mid=(left+right)/2;13}14intstart=left;15left=start;16right=nums.length;17mid=(left+right)/2;18while(left<right){19if(nums[mid]>target){20right=mid;21}22else{23left=mid+1;24}25mid=(left+right)/2;26}27intend=right;28return(start==end)?newint[]{-1,-1}:newint[]{start,end-1};29}30}

关于二分法，还有重要的一个陷阱：

left+right是有可能超出int上下界的！后果话美不看！