二分法查找有序数组

题目链接-来源：力扣（LeetCode）

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

进阶：

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

思路：

已知有序数组，那么大体框架依然是二分法。问题在于，我们二分查找的目标是什么。
举例，对于示例中的 nums = [5,7,7,8,8,10], target = 8，我们需要二分地查找第一个 ‘8’（位于下标 3 处）和最后一个 ‘8’（位于下标 4 处）。这样的话，我们需要实现两套逻辑，两套逻辑都要先二分找到 target（或者确定 target 不存在），然后第一个逻辑定位到最左侧的 target 值，第二个定位到最右侧。
当然，我们也可以进行适当处理，用同一套逻辑覆盖这个问题。比如，我们的查找目标是实现 「二分查找大于等于 target 的第一个数字」的功能，这样我们用同一个逻辑去查找 target 和 target - 1，同样可以完成任务。
时间复杂度：O(logn)
空间复杂度：O(1)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int start = helper(nums, target - 1), end = helper(nums, target) - 1;
        if (end >= start && nums[end] == target) {
            return new int[] {start, end};
        } else {
            return new int[] {-1, -1};
        }
    }
    private int helper(int[] arr, int target) {
        int l = 0, r = arr.length - 1;
        while (l <= r) {
            int mid = l + ((r - l) >> 1);
            int valM = arr[mid];
            if (target >= valM) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }
}