34.在排序数组中查找元素的第一个和最后一个位置

题目:在排序数组中查找元素的第一个和最后一个位置

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

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

• 示例 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 <= 10^5
-10^9 <= nums[i] <= 10^9
nums 是一个非递减数组
-10^9 <= target <= 10^9

• 进阶：

进阶：你可以设计一个时间复杂度为 O(log₂n) 的解决方案吗？

思路

对于普通的二分查找，如果此时我们的nums[mid] = target,但是我们不能确定mid是否为该目标数的左边界，所以此时我们不可以返回下标。例如下面这种情况。

此时mid = 4，nums[mid] = 5,但是此时的mid指向的并不是第一个5，所以我们需要继续查找 ，因为我们要找的是目标数的下边界，所以我们需要在mid的值的左区间继续寻找5，那我们应该怎么做呢？我们只需在target <= nums[mid]时，让right = mid - 1即可，这样我们就可以继续在mid的左区间继续找5。

计算上边界时算是和计算上边界时条件相反，

• 计算下边界时，当target <= nums[mid]时，right = mid -1;target > nums[mid]时，left = mid + 1，返回left。

• 计算上边界时，target >= nums[mid]时，left = mid + 1;当target < nums[mid]时，right = mid -1，返回right。

• 时间复杂度:O(log₂n)

• 空间复杂度:O(1)

代码

public int[] searchRange(int[] nums, int target) { // 总时间复杂度O(log₂n)
    if (nums.length == 0) {
        return new int[]{-1, -1};
    }
    if (nums.length == 1) {
        if (nums[0] == target) {
            return new int[]{0, 0};
        } else {
            return new int[]{-1, -1};
        }
    }
    int begin = binarySearchFirst(nums, target); // 时间复杂度O(log₂n)
    int end = binarySearchLast(nums, target); // 时间复杂度O(log₂n)
    return new int[]{begin, end};
}

private int binarySearchFirst(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        // nums[mid]大于和等于target合并在一起处理，当 nums[mid] >= target 时，我们都移动右指针
        if (nums[mid] >= target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    // left没有越界,且num[left]等于目标值
    if (left < nums.length && nums[left] == target) {
        return left;
    } else {
        return -1;
    }
}

private int binarySearchLast(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        // nums[mid]小于和等于target合并在一起处理，当 nums[mid] <= target 时，我们都移动左指针
        if (nums[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    // right没有越界,且num[right]等于目标值
    if (right >= 0 && nums[right] == target) {
        return right;
    } else {
        return -1;
    }
}