Find First and Last Position of Element in Sorted Array
找有重复数字的左边界:
mid >= target end= mid ,不断缩小右窗口,
最后check start和end的时候,先check start,因为要取左窗口
找有重复数字的右边界:
mid <= target start = mid 不断缩小左窗口
最后check start和end的时候,先check end,因为要取右窗口
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]
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = {-1,-1};
if(nums == null || nums.length == 0)
return res;
res[0] = findLeft(nums,target);
res[1] = findRight(nums,target);
return res;
}
public int findLeft(int[] nums, int target){
int start = 0, end = nums.length-1;
while(start + 1 < end){
int mid = start + (end - start)/2;
if(nums[mid] >= target){
end = mid;
}else{
start = mid;
}
}
if(nums[start] == target){
return start;
}
else if(nums[end] == target){
return end;
}else{
return -1;
}
}
public int findRight(int[] nums,int target){
int start = 0, end = nums.length-1;
while(start + 1 < end){
int mid = start + (end - start)/2;
if(nums[mid] <= target){
start = mid;
}else{
end = mid;
}
}
if(nums[end] == target){
return end;
}
else if(nums[start] == target){
return start;
}else{
return -1;
}
}
}
Last updated