binary search一个特点就是 当condition 是 left <= right的时候 在结尾没找到 left会给该插入的位置... right会给插入的位置的前一位
找左边：一个变化就是 当找到的时候 push right=mid-1,直到 [left,right]没有target..这时候结尾return left给出的插入的位置会是right+1...而现实中是[left, right]+[target, ...., end] target index 刚好就是right+1
右边同理 但是是找应该插入位置的前一个 因为[start...target]+[left,right] 结尾return left给出的插入位置是left..而target 在left-1处
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
37 | public class Solution {
public int[] searchRange(int[] nums, int target) {
int[] result = new int[2];
result[0] = findLeft(nums, target);
result[1] = findRight(nums, target);
return result;
}
int findLeft(int nums[], int target){
int left = 0;
int right = nums.length-1;
while (left <= right){
int mid = (left+right)/2;
if (nums[mid] >= target){
right = mid - 1;
}else{
left = mid + 1;
}
}
if (left >= 0 && left <= nums.length-1 && nums[left] == target) return left;
return -1;
}
int findRight(int nums[], int target){
int left = 0;
int right = nums.length-1;
while (left <= right){
int mid = (left+right)/2;
if (nums[mid] <= target){
left = mid + 1;
}else{
right = mid - 1;
}
}
if (left >= 1 && left <= nums.length && nums[left-1] == target) return left-1;
return -1;
}
}
|
No comments:
Post a Comment