context
binary search运用在sorted array，对于array中出现重复数字或者序列不是单调递增，是分段单调的，就要修改nums[mid] == target时的操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
public int search(int[] nums, int target) {
if(nums.length == 0)
return -1;
int minIdx = findMinIdx(nums);
if(target == nums[minIdx])
return minIdx;
int m = nums.length;
int start = (target <= nums[m - 1]) ? minIdx : 0;
int end = (target <= nums[m - 1]) ? m - 1 : minIdx;
while(start <= end) {
int mid = start + (end - start) / 2;
if(nums[mid] == target)
return mid;
else if(target > nums[mid])
start = mid + 1;
else
end = mid - 1;
}
return -1;
}
public int findMinIdx(int[] nums) {
int start = 0, end = nums.length - 1;
while(start < end) {
int mid = start + (end - start) / 2;
if(nums[mid] > nums[end])
start = mid + 1;
else
end = mid;
}
return start;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public int[] searchRange(int[] nums, int target) {
int[] targetRange = {-1 , -1};
int leftIdx = extremeInsertionIndex(nums, target, true);
if(leftIdx == nums.length || nums[leftIdx] != target)
return targetRange;
targetRange[0] = leftIdx;
targetRange[1] = extremeInsertionIndex(nums, target, false) - 1;
return targetRange;
}
private int extremeInsertionIndex(int[] nums, int target, boolean left) {
int lo = 0;
int hi = nums.length;
while(lo < hi) {
int mid = (lo + hi) / 2;
if(nums[mid] > target || (left && target == nums[mid])) {
hi = mid;
}
else {
lo = mid + 1;
}
}
return lo;
}
}
|