Description
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
如果数组中不存在目标值 target，返回 [-1, -1]。
进阶：
你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？
示例 1：
输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]
示例 2：
输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]
示例 3：
输入：nums = [], target = 0
输出：[-1,-1]
提示：
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109
Solution
- 这里都用左右闭合的方法。
- 简单版思路清晰一些，两段二分代码分别找rightBorder和leftBorder。
- 复杂版，一段二分代码。
- 这两种方案都是进行了两次二分查找。
- 关键在于nums[mid]=target的情况下的条件处理，向右逼近得leftBorder，向左逼近得rightBorder。
[1,2,3,4,5,5,5,6,7,8]
- 比如 left = 1， right = 7， mid = 4
- nums[mid] == nums[4] == 5 == target
- 如果要查找leftBorder， 则 right = mid - 1 = 4
- leftBorder = right = 4 or leftBorder = mid = 5
- 下一步 left <= right (1 <= 4)还未跳出循环
- mid = 2
- nums[mid] == nums[2] == 3 < target
- left = mid + 1 = 3
- 下一步 left <= right (3 <= 4)还未跳出循环
- mid = 3
- nums[mid] == nums[3] == 4 < target
- left = mid + 1 = 4
- 下一步 left <= right (4 <= 4)还未跳出循环
- mid = 4
- nums[mid] == nums[4] == 5 = target
- 如果要查找leftBorder， 则 right = mid - 1 = 3
- leftBorder = right = 3 or leftBorder = mid = 4
- 下一步 跳出循环
- return leftBorder+1 = 4 or leftBorder = 4
简单法
class Solution {
int[] searchRange(int[] nums, int target) {
int rightBorder = getRightBorder(nums, target);
int leftBorder = getLeftBorder(nums, target);
if (rightBorder == -2 || leftBorder == -2) return new int[]{-1,-1};
else if (rightBorder - leftBorder > 1) return new int[]{leftBorder+1, rightBorder-1};
else return new int[]{-1,-1};
}
int getRightBorder(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int rightBorder = -2;
while (left <= right){
int middle = left + (right - left)/2;
if (nums[middle] > target){
right = middle - 1;
} else {
left = middle + 1;
rightBorder = left;
}
}
return rightBorder;
}
int getLeftBorder(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
int leftBorder = -2;
while (left <= right){
int middle = left + (right - left)/2;
if (nums[middle] < target){
left = middle + 1;
} else {
right = middle - 1;
leftBorder = right;
}
}
return leftBorder;
}
};
复杂法
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = new int[] {-1, -1};
res[0] = binarySearch(nums, target, true);
res[1] = binarySearch(nums, target, false);
return res;
}
//leftOrRight为true找左边界 false找右边界
public int binarySearch(int[] nums, int target, boolean leftOrRight) {
int res = -1;
int left = 0, right = nums.length - 1, mid;
while(left <= right) {
mid = left + (right - left) / 2;
if(target < nums[mid])
right = mid - 1;
else if(target > nums[mid])
left = mid + 1;
else {
res = mid;
//处理target == nums[mid]
if(leftOrRight)
right = mid - 1;
else
left = mid + 1;
}
}
return res;
}
}