## Tuesday, July 25, 2017

### LeetCode 34 - Search for a Range

https://leetcode.com/problems/search-for-a-range/
Given an array of integers 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]`.
For example,
Given `[5, 7, 7, 8, 8, 10]` and target value 8,
return `[3, 4]`.

X. https://discuss.leetcode.com/topic/6327/a-very-simple-java-solution-with-only-one-binary-search-algorithm
`````` public int[] searchRange(int[] A, int target) {
int start = Solution.firstGreaterEqual(A, target);
if (start == A.length || A[start] != target) {
return new int[]{-1, -1};
}
return new int[]{start, Solution.firstGreaterEqual(A, target + 1) - 1};
}

//find the first number that is greater than or equal to target.
//could return A.length if target is greater than A[A.length-1].
//actually this is the same as lower_bound in C++ STL.
private static int firstGreaterEqual(int[] A, int target) {
int low = 0, high = A.length;
while (low < high) {
int mid = low + ((high - low) >> 1);
//low <= mid < high
if (A[mid] < target) {
low = mid + 1;
} else {
//should not be mid-1 when A[mid]==target.
//could be mid even if A[mid]>target because mid<high.
high = mid;
}
}
return low;
}``````
`//方法一，采用[]闭区间的方式`
private static int firstGreaterEqual2(int[] A, int target) {
int low = 0, high = A.length - 1;
while (low <= high) {
int mid = low + ((high - low) >> 1);
// low <= mid < high
if (A[mid] < target) {
low = mid + 1;
} else {
high = mid - 1;
}
}
return low;
}

https://discuss.leetcode.com/topic/16486/9-11-lines-o-log-n

X.
http://blog.csdn.net/happyaaaaaaaaaaa/article/details/50846000
1. public int[] searchRange(int[] nums, int target) {
2.     int[] result = {-1, -1};
3.     int index = searchRightIndex(nums, 0, nums.length - 1, target);
4.     if (index < 0 || nums[index] != target)
5.         return result;
6.     result[0] = searchLeftIndex(nums, 0, index, target);
7.     result[1] = index;
8.     return result;
9. }
10. public int searchRightIndex(int[] nums, int left, int right, int target) {
11.     while (left <= right) {
12.         int mid = (left + right) / 2;
13.         if (nums[mid] > target) right = mid - 1;
14.         else left = mid + 1;
15.     }
16.     return right;
17. }
18. public int searchLeftIndex(int[] nums, int left, int right, int target) {
19.     while (left <= right) {
20.         int mid = (left + right) / 2;
21.         if (nums[mid] < target) left = mid + 1;
22.         else right = mid - 1;
23.     }
24.     return left;

1.     public int[] searchRange(int[] nums, int target) {
2.         int[] res = new int[2];
3.         res[0] = bSearchLeft(nums, target, 0, nums.length-1);
4.         res[1] = bSearchRight(nums, target, 0, nums.length-1);
5.         return res;
6.     }
7.     private int bSearchLeft(int[] nums, int target, int left, int right) {
8.         if(left > right) return (left < nums.length && nums[left] == target) ? left : -1;
9.         int mid = (left + right) / 2;
10.         if(nums[mid] < target) return bSearchLeft(nums, target, mid+1, right);
11.         else return bSearchLeft(nums, target, left, mid - 1);
12.     }
13.     private int bSearchRight(int[] nums, int target, int left, int right) {
14.         if(left > right) return (right >= 0 && nums[right] == target) ? right : -1;
15.         int mid = (left + right) / 2;
16.         if(nums[mid] > target) return bSearchRight(nums, target, left, mid-1);
17.         else return bSearchRight(nums, target, mid+1, right);
18.     }
https://all4win78.wordpress.com/2016/09/02/leetcode-34-search-for-a-range/
`    ``public` `int``[] searchRange(``int``[] nums, ``int` `target) {`
`        ``int``[] result = {-``1``, -``1``};`
`        ``if` `(nums == ``null` `|| nums.length == ``0``) {`
`            ``return` `result;`
`        ``}`
`        ``int` `start = ``0``;`
`        ``int` `end = nums.length - ``1``;`
`        ``result[``0``] = findLeft(nums, ``0``, end, target);`
`        ``if` `(result[``0``] != -``1``) {`
`            ``result[``1``] = findRight(nums, result[``0``], end, target);`
`        ``}`
`        ``return` `result;`
`    ``}`
`    `
`    ``private` `int` `findLeft(``int``[] nums, ``int` `start, ``int` `end, ``int` `target) {`
`        ``while` `(start != end) {`
`            ``int` `mid = (end - start) / ``2` `+ start;`
`            ``if` `(nums[mid] >= target) {`
`                ``end = mid;`
`            ``} ``else` `{`
`                ``start = mid + ``1``;`
`            ``}`
`        ``}`
`        ``return` `(nums[start] == target) ? start : -``1``;`
`    ``}`
`    `
`    ``private` `int` `findRight(``int``[] nums, ``int` `start, ``int` `end, ``int` `target) {`
`        ``while` `(start != end) { // scary`
`            ``int` `mid = (end - start) / ``2` `+ start + ``1``;`
`            ``if` `(nums[mid] == target) {`
`                ``start = mid;`
`            ``} ``else` `{`
`                ``end = mid - ``1``;`
`            ``}`
`        ``}`
`        ``return` `start;`
`    ``}`
https://discuss.leetcode.com/topic/21783/easy-java-o-logn-solution
``````public int[] searchRange(int[] nums, int target) {
int[] result = new int[2];
result[0] = findFirst(nums, target);
result[1] = findLast(nums, target);
return result;
}

private int findFirst(int[] nums, int target){
int idx = -1;
int start = 0;
int end = nums.length - 1;
while(start <= end){
int mid = (start + end) / 2;
if(nums[mid] >= target){
end = mid - 1;
}else{
start = mid + 1;
}
if(nums[mid] == target) idx = mid;
}
return idx;
}

private int findLast(int[] nums, int target){
int idx = -1;
int start = 0;
int end = nums.length - 1;
while(start <= end){
int mid = (start + end) / 2;
if(nums[mid] <= target){
start = mid + 1;
}else{
end = mid - 1;
}
if(nums[mid] == target) idx = mid;
}
return idx;
}``````

X. Recursion
https://discuss.leetcode.com/topic/10692/simple-and-strict-o-logn-solution-in-java-using-recursion
``````    public int[] searchRange(int[] A, int target) {
int[] range = {A.length, -1};
searchRange(A, target, 0, A.length - 1, range);
if (range[0] > range[1]) range[0] = -1;
return range;
}

public void searchRange(int[] A, int target, int left, int right, int[] range) {
if (left > right) return;
int mid = left + (right - left) / 2;
if (A[mid] == target) {
if (mid < range[0]) {
range[0] = mid;
searchRange(A, target, left, mid - 1, range);
}
if (mid > range[1]) {
range[1] = mid;
searchRange(A, target, mid + 1, right, range);
}
} else if (A[mid] < target) {
searchRange(A, target, mid + 1, right, range);
} else {
searchRange(A, target, left, mid - 1, range);
}
}``````
X. Inefficient
http://www.programcreek.com/2014/04/leetcode-search-for-a-range-java/
```public int[] searchRange(int[] nums, int target) {
if(nums == null || nums.length == 0){
return null;
}

int[] arr= new int[2];
arr[0]=-1;
arr[1]=-1;

binarySearch(nums, 0, nums.length-1, target, arr);

return arr;
}

public void binarySearch(int[] nums, int left, int right, int target, int[] arr){
if(right<left)
return;

if(nums[left]==nums[right] && nums[left]==target){
arr[0]=left;
arr[1]=right;
return;
}

int mid = left+(right-left)/2;

if(nums[mid]<target){
binarySearch(nums, mid+1, right, target, arr);
}else if(nums[mid]>target){
binarySearch(nums, left, mid-1, target, arr);
}else{
arr[0]=mid;
arr[1]=mid;

//handle duplicates - left
int t1 = mid;
while(t1 >left && nums[t1]==nums[t1-1]){
t1--;
arr[0]=t1;
}

//handle duplicates - right
int t2 = mid;
while(t2 < right&& nums[t2]==nums[t2+1]){
t2++;
arr[1]=t2;
}
return;
}
}```

http://www.bijishequ.com/detail/134759?p=66

``````public int[] searchRange(int[] nums, int target) {
int[] range = new int[]{ -1, -1 };
if (nums.length == 0) {
return range;
}

// 1.Find first occurence of target
int low = 0, high = nums.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] < target) {
low = mid + 1;
} else if (nums[mid] > target) {
high = mid - 1;
} else {
range[0] = mid;
high = mid - 1; // find target, but continue binary search on [low,mid)
}
}

if (range[0] == -1) {
return range;
}

// 2.Find last occurence of target
low = 0; high = nums.length - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
if (nums[mid] < target) {
low = mid + 1;
} else if (nums[mid] > target) {
high = mid - 1;
} else {
range[1] = mid;
low = mid + 1; // find target, but continue binary search on (mid,high]
}
}
return range;
}```
```