侯瑞哲的博客

Ruizhe's Blog

0%

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

发表于 Valine：

题目描述

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

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

你的算法时间复杂度必须是 O(log n) 级别。

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

示例 1:

1
2
输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

示例 2:

1
2
输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

思路

这道题目当然可以给找左边界和右边界各写一个二分查找代码，因为比较简单就不写了。我们来看一下如何用一段代码找到临界索引。

我们有几个前提条件

  1. 数组中可能不出现该值。
  2. 数组中可能有重复元素。

我们来分析一下：

  1. 对于一个元素，我们如果以插入的视角来看的话，这个元素有n+1个插入位置，对应的索引分别是0，1，2...，n。

    1. 如果我们插入的位置，左边都小于该元素，右边都大于等于该元素，那么插入位置的索引，就是第一个大于等于该元素的索引；
    2. 如果我们插入的位置，左边都小于等于该元素，右边都大于该元素，那么插入位置的索引，就是第一个大于该元素的索引，而这个索引减1，就是最后一个小于等于该元素的索引。

  2. 由于数组中可能不存在该值，我们第一步求得第一个大于等于该元素的索引，

    1. 可能为n，也就是说数组中没有大于等于该值的元素
    2. 可能该索引对应的值不是等于该值，而是大于该值

    在这两种情况下，我们就不用再继续求右边的边界了。直接返回-1，-1

  3. 这两种情况，仅仅是对于nums[mid] == target时，采取的策略不同，我们可以用一个参数控制不同的表现

示例代码如下：

1
2
3
4
5
6
7
8
9
def binary_search(nums, target, left):
      l, r = 0, len(nums)
       while l < r:
              mid = l + ((r - l) >> 1)
                if nums[mid] > target or (left and nums[mid] == target):
                        r = mid
               else:
                        l = mid + 1
       return l

这里返回的就是右侧集合的开始位置的下标。

示例代码

这道题的解法如下，加上了不在数组的判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        def binary_search(nums, target, left):
            l, r = 0, len(nums)
            while l < r:
                mid = l + ((r - l) >> 1)
                if nums[mid] > target or (left and nums[mid] == target):
                    r = mid
                else:
                    l = mid + 1
            return l

        left = binary_search(nums, target, True)
        if left == len(nums) or nums[left] != target:
            return [-1, -1]
        return [left, binary_search(nums, target, False) - 1]