对具有重复项的排序列表进行二进制搜索

Question

为了学习分而治之算法，我在 Python 中实现了一个名为 binary_search 的函数，它将获取非空、排序的数字中第一次出现的索引列表（列表的元素是非递减的正整数）。例如，binary_search([1,1,2,2,3,4,4,5,5], 4) == 5、binary_search([1,1,1,1,1], 1) == 0、binary_search([1,1,2,2,3], 5) == -1，其中-1表示在列表中找不到该号码。

以下是我的解决方案。尽管下面的解决方案通过了我手动创建的所有测试，但它未能通过黑盒单元测试器的测试用例。有人可以告诉我下面的代码有什么问题吗？

def find_first_index(A,low,high,key):
    if A[low] == key:
        return low
    if low == high:
        return -1
    mid = low+(high-low)//2
    if A[mid]==key:
        if A[mid-1]==key:
            return find_first_index(A,low,mid-1,key)  
        else:
            return mid
    if key <A[mid]:            
        return find_first_index(A,low,mid-1,key)    
    else: 
        return find_first_index(A, mid+1, high,key)
    
    
def binary_search(keys, number):
    index = find_first_index(A=keys, low=0,high=len(keys)-1,key=number)  
    return(index)

Answer 1

这应该有效：

def find_first_index(A, low, high, key):
    if A[low] == key:
        return low
    if low == high:
        return -1
    mid = low + (high - low) // 2
    if A[mid] >= key:
        return find_first_index(A, low, mid, key)
    return find_first_index(A, mid + 1, high, key)


def binary_search(keys, number):   
    return find_first_index(keys, 0, len(keys) - 1, number)

正如您已经意识到的那样，您的解决方案不起作用。例如，它用以下输入中断：

>>> binary_search([1, 5], 0)
...
RecursionError: maximum recursion depth exceeded in comparison

如您所见，该函数甚至没有终止，这里正在进行无限递归。尝试在一张纸上“运行”您的程序以了解发生了什么（或使用调试器），它非常具有形成性。

那么，错误是什么？问题是从某个函数调用开始 high < low。在这种特定情况下，在第一个函数调用 low == 0 和 high == 1 中。然后mid = 0（因为int(low + (high - low) / 2) == 0）。但是你调用 find_first_index(A, low, mid - 1, key)，基本上就是 find_first_index(A, 0, -1, key)。随后的调用将完全相同（因为使用 low == 0 和 high == -1 您将再次使用 mid == 0）。因此，你有一个无限递归。

在这种情况下，一个简单的解决方案是

if low >= high:
    return -1

或者只使用我以前的解决方案：在我看来检查 mid - 1 不是一个好主意，或者至少在这样做时你必须更加小心。

对具有重复项的排序列表进行二进制搜索

Binary Search on Sorted List with Duplicates

python

algorithm

divide-and-conquer