递归调用中索引超出范围（二分查找）

Question

我一直在尝试解决这个leetcode问题。问题是在非递减列表中找到目标值的范围。我正在使用二分搜索在列表中搜索目标值，然后在退出递归调用时从该索引中“涟漪”出来，以查看此处是否有该目标的任何重复实例并返回范围。我的问题是，当我尝试运行代码时，leetcode 编译器给了我一个非常奇怪的索引超出范围错误。这是我的代码：

class Solution(object):
    def searchRange(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """

        # Recursive Count (counts the number of recursive exits)
        RC = [0]
        length = len(nums) -1

        def getRange(left, right, nums):
            if(left == right):
                # Base case reached
                return [left, right]

            mid = (left + right) // 2
            indices = []

            # Searching for the middlle target index
            if (nums[mid] == target):
                indices = getRange(mid, mid, nums)
            elif (nums[mid] < target):
                indices = getRange(mid + 1, right, nums)
            elif (nums[mid] > target):
                indices = getRange(left, mid - 1, nums)
            
            # Ripling (as the program exits the last recursive call)
            if  indices[0] != 0 and nums[indices[0]] - RC[0] == target:
                indices[0] = indices[0] - 1
            elif indices[1] != length and nums[indices[1]] + RC[0] == target:
                indices[1] = indices[1] + 1

            RC[0] = RC[0] + 1
            return indices

        return getRange(0, length, nums)

这是错误：

IndexError: list index out of range
    if (nums[mid] == target):
Line 22 in getRange (Solution.py)
    return getRange(0, length, nums)
Line 38 in searchRange (Solution.py)
    ret = Solution().searchRange(param_1, param_2)
Line 66 in _driver (Solution.py)
    _driver()
Line 76 in <module> (Solution.py)

它突出显示第 22 行是问题所在。就是这一行：

if (nums[mid] == target):

我不明白为什么 nums[mid] 超出范围。 mid 的计算很简单（左+右）/2，因此对于非递减顺序的列表，mid 应该不可能超出范围。我已经用 leetcode 的输入值仔细跟踪了迭代，程序的行为完全符合我在纸上的预期。

起初我使用 nums 的全局变量，我认为编译器可能正在为二分搜索算法的每个递归调用创建 nums 数组的新子部分，因此我将原始 nums 数组传递到每个递归调用中。不幸的是，这并没有解决问题。

Answer 1

错误的直接原因是，对于空列表作为输入，检查

left == right

不会为真，然后你的代码继续访问

nums[mid]

，这是无效的。

但是退一步来说，你的算法是行不通的。

RC

无法帮助正确更新

indices

，就好像您只会以 1 为步长缩小列表范围（这不是二分搜索的作用）。以输入

[1, 1, 1, 1, 1, 1]

并找到 1...

为例

您需要的是两次二分搜索：一个将找到具有目标值的子列表的 start，另一个将找到同一子列表的 end。