1、前言
题目描述2、思路
思路就是对左右两边都进行二分查找,确定左右边界。即对数组进行两次二分查找,首先对数组进行二分查找,确定左边界。确定左边界的方法是,如果遇到 nums[mid] == target,此时不需要返回,而是把右边界往左缩,即 right = mid - 1。while 循环条件是 left <= right,即 right 会减到 left > right,跳出循环。有人会怀疑将边界往左锁 right = mid - 1 会使得 left 不能到 target 的左边界去。不会出现这种情况,right 最终会到左边界的上一位,然后 left 最终会与 right 相等。当 left 到达左边界时,left > right 会跳出循环,所以 left 会是左边界。
还有一种简单的方法是,找到 target 后,定义两个指针不断向两边扩展,但是这种扩展的方法确实没有二分快。但是如果想不出来,而是用扩展的方法吧,解出题还是好的。
3、代码
class Solution {
public int[] searchRange(int[] nums, int target) {
if(nums == null || nums.length == 0){
return new int[]{-1,-1};
}
int start = leftSearch(nums,target);
if(start == -1){
return new int[]{-1,-1};
}
int end = rightSearch(nums,target);
return new int[]{start,end};
}
int leftSearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 别返回,收缩左侧边界
right = mid - 1;
}
}
// 最后要检查 left 越界的情况
if (left >= nums.length || nums[left] != target)
return -1;
return left;
}
int rightSearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid - 1;
} else if (nums[mid] == target) {
// 别返回,收缩右侧边界
left = mid + 1;
}
}
// 最后要检查 right 越界的情况
if (right < 0 || nums[right] != target)
return -1;
return right;
}
}
public class Q34_SearchRange {
public int[] searchRange(int[] nums, int target) {
if(nums == null || nums.length == 0){
return new int[]{-1, -1};
}
int mid = binarySearch(nums, target);
if(mid == -1){
return new int[]{-1, -1};
}
int left = mid, right = mid;
while((left - 1 >= 0 && nums[left - 1] == nums[left]) || (right + 1 <= nums.length - 1 && nums[right] == nums[right + 1])){
if(left - 1 >= 0 && nums[left - 1] == nums[left]){
left--;
}
if(right + 1 <= nums.length && nums[right] == nums[right + 1]){
right++;
}
}
return new int[]{left, right};
}
private int binarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while(left <= right){
int mid = (right - left) / 2 + left;
if(nums[mid] == target){
return mid;
}else if(nums[mid] > target){
right = mid - 1;
}else if(nums[mid] < target){
left = mid + 1;
}
}
return -1;
}
public static void main(String[] args) {
int[] nums = {1};
int target = 1;
int[] res = new Q34_SearchRange().searchRange(nums, target);
System.out.println(res[0] + ":" + res[1]);
}
}
网友评论