image.png
AC代碼
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] ans = new int[2];
ans[0] = -1;
ans[1] = -1;
if(nums == null || nums.length == 0) {
return ans;
}
int outLeft = 0;
int outRight = nums.length - 1;
while(outLeft <= outRight) {
int mid = outLeft + (outRight - outLeft) / 2;
if(nums[mid] == target) {
ans[0] = findLeft(nums, target, outLeft, mid);
ans[1] = findRight(nums, target, mid, outRight);
return ans;
}else if(nums[mid] > target) {
outRight = mid - 1;
}else {
outLeft = mid + 1;
}
}
return ans;
}
private int findLeft(int[] nums, int target, int left, int right) {
int ans = right;
while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] == target) {
ans = mid;
right = mid - 1;
}else if(nums[mid] < target){
left = mid + 1;
}
}
return ans;
}
private int findRight(int[] nums, int target, int left, int right) {
int ans = left;
while(left <= right) {
int mid = left + (right - left) / 2;
if(nums[mid] == target) {
ans = mid;
left = mid + 1;
}else if(nums[mid] > target){
right = mid - 1;
}
}
return ans;
}
}
精髓
AC代碼看起來(lái)比較復(fù)雜，邏輯比較清楚
首先普通二分查找，找到第一個(gè)target郊尝，如果找不到就是沒(méi)有，就直接返回
然后分別向左和向右查找區(qū)間左端點(diǎn)和右端點(diǎn)战惊，都是基于二分的思想
