优质博文IT-BLOG-CN

一、题目

给你一个按照非递减顺序排列的整数数组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

二、代码

方案一：二分查找

直观的思路肯定是从前往后遍历一遍。用两个变量记录第一次和最后一次遇见target的下标，但这个方法的时间复杂度为O(n)，没有利用到数组升序排列的条件。

由于数组已经排序，因此整个数组是单调递增的，我们可以利用二分法来加速查找的过程。

考虑target开始和结束位置，其实我们要找的就是数组中「第一个等于target的位置」（记为leftIdx）和「第一个大于target的位置减一」（记为rightIdx）。

二分查找中，寻找leftIdx即为在数组中寻找第一个大于等于target的下标，寻找rightIdx即为在数组中寻找第一个大于target的下标，然后将下标减一。两者的判断条件不同，为了代码的复用，我们定义binarySearch(nums, target, lower)表示在nums数组中二分查找target的位置，如果lower为true，则查找第一个大于等于target的下标，否则查找第一个大于target的下标。

最后，因为target可能不存在数组中，因此我们需要重新校验我们得到的两个下标leftIdx和rightIdx，看是否符合条件，如果符合条件就返回[leftIdx,rightIdx]，不符合就返回[−1,−1]。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int leftIdx = binarySearch(nums, target, true);
        int rightIdx = binarySearch(nums, target, false) - 1;
        if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) {
            return new int[]{leftIdx, rightIdx};
        } 
        return new int[]{-1, -1};
    }

    public int binarySearch(int[] nums, int target, boolean lower) {
        int left = 0, right = nums.length - 1, ans = nums.length;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (nums[mid] > target || (lower && nums[mid] >= target)) {
                right = mid - 1;
                ans = mid;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }
}

方案二：小于等于目标值的搜索策略

class Solution {
    public int[] searchRange(int[] nums, int target) {
        // 首个target如果存在，一定是最后小于等于target-1的元素的后一位
        int start = search(nums, target - 1) + 1;
        if(start == nums.length || nums[start] != target){
            return new int[]{-1, -1};    // 首个target不存在，即数组中不包含target
        }
        // 找到最后小于target的元素，即为最后一个target
        int end = search(nums, target);
        return new int[]{start, end};
    }

    /**
     * 返回最后小于等于target的元素索引，如果不存在，返回-1
     * @param nums: 输入数组
     * @param target: 目标值
     * @return: 目标值索引
    */
    private int search(int[] nums, int target){
        // 二分查找区间[left, right)，初始为整个区间
        int left = 0;   
        int right = nums.length;
        // 找到最后小于等于target的值
        while(left < right){
            int mid = left + ((right - left) >> 1);
            if(nums[mid] <= target){
                left = mid + 1;  // 找到一个小于等于target的值，暂存并在右半区间继续查找更大的小于target的值
            }else{
                right = mid;    // 没有找到小于等于target的值，则在左半区间去寻找更小的数
            }
        }
        return left - 1;    // left始终为暂存结果的后一位
    }
}

方案三：两次二分法查找左右边界

这道题目可以使用两次二分查找来分别确定左右边界。这里以左边界为例，我们判断一个位置是左边界需要满足以下两个条件：
【1】该位置值为target；
【2】该位置左边的元素小于他，或者该位置的下标为0；

所以，根据这个思路，只需要简单的修改一下二分查找的逻辑就可以找到左边界，代码如下：

def searchLeft(nums, target):
            # 左边界需要满足两个条件：
            # 1. 他的值为target
            # 2. 他的左边元素小于他，或者他的下标为0
            left, right = 0, len(nums)-1
            while left <= right:
                mid = (right-left)//2 + left
                if nums[mid] == target:
                    if mid == 0 or nums[mid-1] < target:
                        return mid
                    else:
                        right = mid - 1
                elif nums[mid] > target:
                    right = mid - 1
                else:
                    left = mid + 1
            return -1

整体思路只是在if nums[mid] == target时多加了一步判断，如果不是起始位置，那么起始位置一定在mid左侧，所以需要同时修改right = mid - 1。

同样的，右边界的位置需要满足：
【1】该位置值为target；
【2】该位置右边的元素小于他，或者该位置的下标为len(nums)-1。

也只需要稍微修改一下二分查找的代码就可以，最后完整代码如下：

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def searchLeft(nums, target):
            # 左边界需要满足两个条件：
            # 1. 他的值为target
            # 2. 他的左边元素小于他，或者他的下标为0
            left, right = 0, len(nums)-1
            while left <= right:
                mid = (right-left)//2 + left
                if nums[mid] == target:
                    if mid == 0 or nums[mid-1] < target:
                        return mid
                    else:
                        right = mid - 1
                elif nums[mid] > target:
                    right = mid - 1
                else:
                    left = mid + 1
            return -1
        
        def searchRight(nums, target):
            # 右边界需要满足两个条件：
            # 1. 他的值为target
            # 2. 他的右边元素大于他，或者他的下标为len(nums)-1
            left, right = 0, len(nums)-1
            while left <= right:
                mid = (right-left)//2 + left
                if nums[mid] == target:
                    if mid == len(nums)-1 or nums[mid+1] > target:
                        return mid
                    else:
                        left = mid + 1
                elif nums[mid] > target:
                    right = mid - 1
                else:
                    left = mid + 1
            return -1

        return [searchLeft(nums, target), searchRight(nums, target)]