最后一遍-L34-Find First and Last Position of Element in Sorted Array
LeetCode 34. Find First and Last Position of Element in Sorted Array
如果使用O(n)的遍历，根本就不会有什么难度了，但是题目中已经明确的标注了：Sorted Array，那么就不行了。
描述：
Given an array of integers nums 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].
Example 1:
Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]
Example 2:
Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]
思路：
那就使用二分查找出第一个值，最后一个值。原本的思路。
具体的代码如下：首先是按照思路来的，一种类似作弊的思路，前后加减0.5
public int[] searchRange(int[] nums, int target) {
double left = target - 0.5, right = target + 0.5;
int l = bs(nums, left), r = bs(nums, right);
if(l == r) return new int[]{-1, -1};
return new int[]{l, r-1};
}
public int bs(int[] nums, double target) {
int l = 0, h = nums.length-1;
while(l <= h){
int m = l + (h - l)/2;
if(target > nums[m]) l = m+1;
else h = m-1;
}
return l;
}
另外就是根据二分查找的方法，进行进一步的梳理，确定在二分的时候，碰到等于情况的处理：
public class L34 {
public static void main(String[] args) {
System.out.println(Arrays.toString(searchRange(new int[]{5,7,7,7,7,7,7,10},7)));
}
public static int[] searchRange(int[] nums, int target) {
int[] result = new int[2];
result[0]=findFirstIndex(nums,target);
result[1]=findLastIndex(nums,target);
return result;
}
private static int findFirstIndex(int[] nums, int target) {
int from = 0,to=nums.length,mid=0,in=-1;
while(from <= to){
mid = from+(to-from)/2;
if(nums[mid] == target){
in=mid;
to = mid-1;
} else if (nums[mid] > target) {
to=mid-1;
}else{
from = mid+1;
}
}
return in;
}
private static int findLastIndex(int[] nums, int target) {
int from = 0,to=nums.length,mid=0,in=-1;
while(from <= to){
mid = from+(to-from)/2;
if(nums[mid] == target){
in=mid;
from = mid+1;
} else if (nums[mid] > target) {
to=mid-1;
}else{
from = mid+1;
}
}
return in;
}
}
正规的思路分析：
The problem can be simply broken down as two binary searches for the begining and end of the range, respectively:
First let’s find the left boundary of the range. We initialize the range to [i=0, j=n-1]. In each step, calculate the middle element [mid = (i+j)/2]. Now according to the relative value of A[mid] to target, there are three possibilities:
If A[mid] < target, then the range must begins on the right of mid (hence i = mid+1 for the next iteration) If A[mid] > target, it means the range must begins on the left of mid (j = mid-1) If A[mid] = target, then the range must begins on the left of or at mid (j= mid) Since we would move the search range to the same side for case 2 and 3, we might as well merge them as one single case so that less code is needed:
2*. If A[mid] >= target, j = mid;
Surprisingly, 1 and 2* are the only logic you need to put in loop while (i < j). When the while loop terminates, the value of i/j is where the start of the range is. Why?
No matter what the sequence originally is, as we narrow down the search range, eventually we will be at a situation where there are only two elements in the search range. Suppose our target is 5, then we have only 7 possible cases:
case 1: [5 7] (A[i] = target < A[j]) case 2: [5 3] (A[i] = target > A[j]) case 3: [5 5] (A[i] = target = A[j]) case 4: [3 5] (A[j] = target > A[i]) case 5: [3 7] (A[i] < target < A[j]) case 6: [3 4] (A[i] < A[j] < target) case 7: [6 7] (target < A[i] < A[j]) For case 1, 2 and 3, if we follow the above rule, since mid = i => A[mid] = target in these cases, then we would set j = mid. Now the loop terminates and i and j both point to the first 5.
For case 4, since A[mid] < target, then set i = mid+1. The loop terminates and both i and j point to 5.
For all other cases, by the time the loop terminates, A[i] is not equal to 5. So we can easily know 5 is not in the sequence if the comparison fails.
In conclusion, when the loop terminates, if A[i]==target, then i is the left boundary of the range; otherwise, just return -1;
For the right of the range, we can use a similar idea. Again we can come up with several rules:
If A[mid] > target, then the range must begins on the left of mid (j = mid-1) If A[mid] < target, then the range must begins on the right of mid (hence i = mid+1 for the next iteration) If A[mid] = target, then the range must begins on the right of or at mid (i= mid) Again, we can merge condition 2 and 3 into:
2* If A[mid] <= target, then i = mid; However, the terminate condition on longer works this time. Consider the following case:
[5 7], target = 5 Now A[mid] = 5, then according to rule 2, we set i = mid. This practically does nothing because i is already equal to mid. As a result, the search range is not moved at all!
The solution is by using a small trick: instead of calculating mid as mid = (i+j)/2, we now do:
mid = (i+j)/2+1 Why does this trick work? When we use mid = (i+j)/2, the mid is rounded to the lowest integer. In other words, mid is always biased towards the left. This means we could have i == mid when j - i == mid, but we NEVER have j == mid. So in order to keep the search range moving, you must make sure the new i is set to something different than mid, otherwise we are at the risk that i gets stuck. But for the new j, it is okay if we set it to mid, since it was not equal to mid anyways. Our two rules in search of the left boundary happen to satisfy these requirements, so it works perfectly in that situation. Similarly, when we search for the right boundary, we must make sure i won’t get stuck when we set the new i to i = mid. The easiest way to achieve this is by making mid biased to the right, i.e. mid = (i+j)/2+1.
All this reasoning boils down to the following simple code:
具体点的代码：
public static int[] searchRange_iterator(int[] nums,int target){
int[] result = new int[]{-1,-1};
if(nums == null || nums.length == 0) return result;
int from =0,to=nums.length-1;
while(from < to){
int mid = from+(to-from)/2;
if(nums[mid] < target) from=mid+1;
else to=mid;
}
if(nums[from] == target) result[0]=from;
else return result;
to = nums.length-1;
while(from < to){
int mid = from+(to-from)/2+1; // 这个地方非常的重要
if(nums[mid] > target) to = mid-1;
else from=mid;
}
result[1]=to;
return result;
}