Searchforarange尋找上下界-Leetcode

2019-11-14 15:36:52

字體：大中小

來源：轉載

供稿：網友

原題如下：

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)的復雜度了。

后來在別人的答案里看到一個非常巧妙的實現，利用了二分法的一點變化。傳統的二分法采用如下結構：

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

在這個題目中，我們不是要找到一個特定的元素，而是要找到這樣一組元素的上下界。那就要對二分法進行修改。

不再是找到相等元素就跳出循環，而是找到相等元素就繼續把邊界向另一端推進，直到推進到相等元素的最后一個為止。

這樣一來，我們只需運行兩次方向不同的二分就可以找到上下界了。

代碼如下：

 1 public class Solution { 2     public int[] searchRange(int[] nums, int target) { 3         int left=0,right=nums.length;//注意 右邊界不是取的nums.length-1。這是為了方便做第29行的判斷. 4         int mid=(left+right)/2; 5         while(left<right){ 6             if(nums[mid]>=target){ 7                 right=mid; 8             } 9             else{10                 left=mid+1;11             }12             mid=(left+right)/2;13         }14         int start=left;15         left=start;16         right=nums.length;17         mid=(left+right)/2;18         while(left<right){19             if(nums[mid]>target){20                 right=mid;21             }22             else{23                 left=mid+1;24             }25             mid=(left+right)/2;26         }27         int end=right;28         return (start==end)?new int[]{-1,-1}:new int[]{start,end-1};29     }30 }