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

标签: 数组 二分查找

难度: Medium

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

Submission

运行时间: 48 ms

内存: 15.5 MB

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        ans = [-1, -1]
        if len(nums) == 0:
            return ans

        l = 0
        r = len(nums) - 1
        while l < r:
            mid = l + (r - l) // 2
            if nums[mid] >= target:
                r = mid
            else:
                l = mid + 1

        if nums[l] == target:
            ans[0] = l
            l = 0
            r = len(nums) - 1
            while l < r:
                mid = l + (r - l + 1) // 2
                if nums[mid] <= target:
                    l = mid
                else:
                    r = mid - 1
            if nums[l] == target:
                ans[1] = l

        return ans

Explain

这个题解使用二分查找的思路来寻找目标值的开始位置和结束位置。首先用一次二分查找寻找目标值的左边界,即第一个大于等于目标值的位置。如果找到目标值,则再用一次二分查找寻找目标值的右边界,即最后一个小于等于目标值的位置。最后返回找到的左右边界作为结果。如果没有找到目标值,则返回[-1, -1]。

时间复杂度: O(log n)

空间复杂度: O(1)

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        ans = [-1, -1]
        if len(nums) == 0:
            return ans
        
        # 二分查找目标值的左边界
        l = 0
        r = len(nums) - 1
        while l < r:
            mid = l + (r - l) // 2
            if nums[mid] >= target:
                r = mid
            else:
                l = mid + 1
        
        # 如果找到目标值,则继续查找右边界
        if nums[l] == target:
            ans[0] = l
            l = 0
            r = len(nums) - 1
            while l < r:
                mid = l + (r - l + 1) // 2
                if nums[mid] <= target:
                    l = mid
                else:
                    r = mid - 1
            if nums[l] == target:
                ans[1] = l
        
        return ans

Explore

在二分查找中设置r为mid而不是mid-1是为了确保不会错过目标值的左边界。如果设置r为mid-1,当mid处于目标值的左边界时,我们将其排除在新的搜索范围之外,从而错过正确的边界。通过设置r为mid,我们保证包含可能的左边界在新的搜索范围内,从而允许算法继续逼近,直到找到确切的左边界。此方法确保每次迭代都缩小搜索范围,同时不会跳过左边界。

在寻找右边界时,当nums[mid] <= target,更新左边界l为mid(而不是mid - 1)是为了确保包含目标值的右边界在搜索范围内。这种处理允许搜索范围逐渐收缩而不排除可能的右边界,从而避免错过任何有效的边界。如果将l设置为mid-1,可能会导致漏掉目标值的实际右边界。这种策略确保算法在逼近目标值的右边界时,始终保持正确的搜索范围。

调整mid的计算方式为mid = l + (r - l + 1) // 2主要是为了确保在二分查找中mid偏向右侧,特别是当l和r非常接近时。这种偏向右侧的策略有助于防止算法陷入无限循环,并确保能够正确找到目标值的右边界。特别是在目标值连续出现且位于数组末尾的情况下,这种调整确保算法能够继续向右逼近,直到找到最后一个目标值的位置。

是的,这种二分查找方法能够准确返回正确的边界值,即使目标值位于数组的开始或结束位置。算法首先确定左边界,确保不会错过开始处的目标值;然后确定右边界,同样确保包括结束处的目标值在内。因此,无论目标值位于数组的哪个位置,该方法都能有效地找到并返回正确的边界值。