LeetCode 34 - Search for a Range

作者 QIFAN 日期 2017-01-14
LeetCode 34 - Search for a Range

原题链接: 34. Search for a Range


题干

给定一个已排序(有重复)的数组 nums ,和一个目标值 target ,返回该 target 在该数组中的位置范围。若没有找到,返回 (-1, -1) 。要求时间复杂度 $O(logn)$ 。

思路

首先想到二分查找。

如何确定左右边界?改变 base case : 如果 hi < target || lo > target 返回。

在进入下一层二分查找时:

  • nums[mid] == target
    • nums[lo] == target 。左边界为 lo 与目前左边界的最小值。
    • nums[lo] < target 。在 (lo, mid - 1) 里寻找左边界。
    • nums[hi] == target 。右边界为 hi 与目前右边界的最大值。
    • nums[hi] > target 。在 (mid + 1, hi) 里寻找右边界。

代码:

public int[] searchRange(int[] nums, int target) {
int[] res = new int[2];
res[0] = nums.length;
res[1] = -1;
binarySearch(res, target, nums, 0, nums.length - 1);
if (res[0] == nums.length) {
res[0] = -1;
}
return res;
}
public void binarySearch(int[] res, int target, int[] nums, int lo, int hi) {
if (lo > hi) {
return;
}
int mid = lo + (hi - lo) / 2;
if (nums[mid] == target) {
res[0] = Math.min(mid, res[0]);
res[1] = Math.max(mid, res[1]);
if (nums[lo] == target) {
res[0] = Math.min(lo, res[0]);
} else {
binarySearch(res, target, nums, lo, mid - 1);
}
if (nums[hi] == target) {
res[1] = Math.max(hi, res[1]);
} else {
binarySearch(res, target, nums, mid + 1, hi);
}
} else if (nums[mid] < target) {
binarySearch(res, target, nums, mid + 1, hi);
} else {
binarySearch(res, target, nums, lo, mid - 1);
}
}