题目描述
思路：
二分查找之寻找左右侧边界
两个关键点：1. 数组有序；2. 时间复杂度O(log n)
方法一：
class Solution {
public int[] searchRange(int[] nums, int target) {
if (nums.length == 0 || nums == null) {
return new int[]{-1, -1};
}
int leftBound = -1;
// 寻找最左边界
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (target == nums[mid]) {
if (mid == 0 || nums[mid - 1] != target) {
leftBound = mid;
break;
} else {
right = mid - 1;
}
} else if (target < nums[mid]) {
right = mid - 1;
} else if (target > nums[mid]) {
left = mid + 1;
}
}
// 说明没有找到左边界,此时直接返回[-1, -1]
if (leftBound == -1) {
return new int[]{-1, -1};
}
// 开始寻找右边界
left = 0;
right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (target == nums[mid]) {
if (mid == nums.length - 1 || nums[mid + 1] != target) {
return new int[]{leftBound, mid};
} else {
left = mid + 1;
}
} else if (target < nums[mid]) {
right = mid - 1;
} else if (target > nums[mid]) {
left = mid + 1;
}
}
return new int[]{-1, -1};
}
}