二分查找重复元素的范围 Leetcode 34

在上一篇文章中（ 二分查找法搜寻元素 Leetcode35, Leetcode69 ），我们分析了二分查找法的两种经典思路。现在我们再来挑战一下更复杂的情况：Leetcode 34. 在排序数组中查找元素的第一个和最后一个位置。这道题的数组中可能有重复元素，需要求出值为 target 的元素范围，以 [ 第一个值为 target 的元素索引, 最后一个值为 target 的元素索引 ] 的方式返回。如果没有，就返回 [ -1, -1]。

在此之前，我们都是把二分查找法用于无重复元素的排序数组中搜寻，每个元素的值都是唯一的，只有找到和找不到两种可能。而这道题难在要求出重复元素的范围，也就是说，找到一个值为 target 的元素也不一定符合要求。解决这类问题的关键点在于：当搜寻区间的中间点取值等于 target 时，我们不能止步于此，还要继续搜寻它的左右区间有没有等于 target 的元素，以此来找到重复元素范围的起点和终点。

建议您先看一下上一篇文章（二分查找法搜寻元素 Leetcode35, Leetcode69）的第二部分：查找取值与 target 最接近的元素，对于理解这个题目的解决思路有帮助。

方法一、标准二分查找法 while left <= right

基于标准二分查找 ( while left <= right )，做了一点改动：当 nums[middle] 的值等于 target 时，不能马上返回 middle 结束循环，用一个 index 变量（初始设为 -1）保存此时的 middle 值，然后：

• 搜索起始点：要在左区间 [ left, middle - 1] 继续搜寻有没有等于 target 的元素。因此，当 nums[middle] == target 时，设置 index = middle, right = middle - 1。

  while 循环结束时，index 的值就是所能找到的等于 target 的元素的最小索引，也就是我们要找的起始点。

• 搜索终止点：要在右区间 [ middle +1, right ] 继续搜寻有没有等于 target 的元素。因此，当 nums[middle] == target 时，设置 index = middle, left = middle + 1。

  while 循环结束时，index 的值就是所能找到的等于 target 的元素的最大索引，也就是我们要找的终止点。

对比这两次查找会发现，搜索起始点和搜索终止点的二分查找在处理 nums[middle] 不等于 target 时的操作完全一样，只是在 nums[middle] 等于 target 时有不同：要根据找起点或终点来决定是继续在左区间或右区间搜寻。为了减少重复代码，可以用一个函数 searchTarget 来实现两次查找，设置一个 Boolean 变量 isSearchFirst 来标识搜寻起点或终点。具体 Python 代码如下：

# 数组为空的情况
if not nums:
    return [-1, -1]

def searchTarget(nums, target, isSearchFirst):
    # 用idx保存等于target的middle元素
    # 初始值为-1
    idx = -1
    left, right = 0, len(nums) - 1
    while left <= right:
        middle = left + (right - left) // 2

        if nums[middle] == target:
            idx = middle
            # 寻找起点和终点的二分查找代码只有这里不同
            # isSearchFirst为True,搜寻起点。
            # 下一步在左区间搜寻
            if isSearchFirst:
                right = middle - 1
            # isSearchFirst为False,搜寻终点
            # 下一步在右区间搜寻
            else:
                left = middle + 1

        elif nums[middle] < target:
            left = middle + 1
        else:
            right = middle - 1
            
    return idx


# 搜寻元素起始点
firstPos = searchTarget(nums, target, True)
# 如果没找到，直接返回 [-1, -1]
if firstPos == -1:
    return [-1,-1]
else:
    # 搜寻元素终点
    lastPos = searchTarget(nums, target, False)
    return [firstPos, lastPos] 

方法二、二分查找法之二 while left < right

这个方法 while 循环的条件是 left < right，与上述方法在 nums[middle] 的值等于 target 时的处理类似，不同之处：1.这个方法没有用变量保存索引，而是循环结束后再判断得到 ；2.下一步的搜寻区间包含了 middle：

• 搜索起始点：在包含 middle 的左区间 [ left, middle ] 继续寻找，因此设置 right = middle。这个操作与 nums[middle] > target 时可以合并为：当 nums[middle] >= target 时，right = middle。当 nums[middle] < target 时，left = middle + 1。

  循环结束后，如果 nums[left] == target（left 或 right 均可，因为 left = right），left 就是我们要找的起点，否则说明数组中没有值为 target 的元素。

• 搜索终止点：在包含 middle 的右区间 [ middle, right ] 继续寻找，因此设置 left = middle。这个操作与 nums[middle] < target 时可以合并为：当 nums[middle] <= target 时，left = middle。当 nums[middle] > target 时，right = middle - 1。

  这里有一个问题：while 循环到只有两个元素时，如果按照原有的求解 middle 方式，middle = left。当 nums[middle] <= target 时，又有 left = middle，这样没有更新搜寻区间，循环无法停止。解决方式很巧妙：设置 middle = ( left + right ) / 2 + 1，把 middle 往右边偏移。最后一次循环时有 middle = right，循环可以终止。

  循环结束后，left 就是我们要找的终点。

Python 代码如下：

# 数组为空的情况
if not nums:
    return [-1, -1]

# result数组保存返回索引
result = [-1, -1]

# 确定重复元素起点的搜寻区间
left, right = 0, len(nums) - 1
while left < right:
    middle = left + (right - left) // 2
    if nums[middle] >= target:
        # 继续在左区间[left, middle]搜寻
        right = middle                
    else:                
        left = middle + 1
if nums[left] != target:
    return result
else:
    result[0] = left
    
# 确定重复元素终点的搜寻区间
# 此时区间的起点left就设置为刚找到的起点
right = len(nums) - 1
while left < right:
    middle = left + (right - left + 1) // 2
    if nums[middle] <= target:
        # 继续在右区间[middle, right]搜寻
        left = middle 
    else:
        right = middle - 1
result[1] = left

return result

本文对您有帮助的话，请点赞支持一下吧，谢谢！

关注我 宁萌Julie，互相学习，多多交流呀！

参考：

1.方法一思路：Easy java O(logn) solution

2.方法二思路：Clean iterative solution with two binary searches