BiruLyu
7/29/2017 - 5:18 PM

## 34. Search for a Range(#).java

``````public class Solution {
public int[] searchRange(int[] nums, int target) {
int[] range = {nums.length - 1, -1}; // {6, -1}
helper(nums, target, 0 , nums.length - 1, range);
if(range[0] > range[1]){
range[0] = -1;
}
return range;
}

public void helper(int[] nums, int target, int start, int end, int[] range){
if(start > end){
return;
}
int mid = start + (end - start)/2;
if(nums[mid] == target){
if(mid < range[0]){
range[0] = mid;
helper(nums, target, start, mid - 1, range);
}
if(mid > range[1]){
range[1] = mid;
helper(nums, target, mid + 1, end, range); // 5, 5
}
} else if(nums[mid] < target){
helper(nums, target, mid + 1, end, range);
} else{
helper(nums, target, start, mid - 1, range);
}
}
}``````
``````public class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = new int[2];
Arrays.fill(res, -1);
if (nums == null || nums.length < 1) return res;
int len = nums.length;
int i = 0;
int j = len - 1;
while (i < j) {
int mid = i + (j - i) / 2;
if (nums[mid] < target) {
i = mid + 1;
} else {
j = mid;
}
}
if (nums[i] != target) return res;
else res[0] = i;

j = len - 1;
while (i < j) {
int mid = i + (j - i) / 2 + 1;
/*
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
*/
if (nums[mid] > target) {
j = mid - 1;
} else {
i = mid;
}
}
res[1] = j;
return res;
}
}``````