尝试修复 IndexError 时增加了二分搜索的运行时间

Question

我最近关注了有关二分搜索的 YouTube 教程，当我运行 YouTube 用户构建的代码时，遇到了列表索引超出范围的问题。据我所知，我确实做了他们所做的事情，现在我想知道我做错了什么。我尝试删除“if list[midpoint] == target:”作为“if midpoint == target:”，但这打开了另一罐蠕虫，其中中点缓慢增加，使得代码比我预期的慢得多......下面是代码：

def binary_search(list, target, low=None, high=None):
    if low is None:
        low = list[0]
    if high is None:
        high = list[-1]
    midpoint = (low+high) // 2

    if high < low:
        return print("Target was not in the list")
    if list[midpoint] == target:
        return midpoint
    elif target < list[midpoint]:
        return binary_search(list, target, low, midpoint-1)
        # new max == midpoint-1 (because it was not the target)
    else:
        return binary_search(list, target, midpoint+1, high)
        # new min == midpoint+1 (because it was not the target)`

if __name__ == '__main__':
    # tests how fast the binary search is by randomly generating a sorted list
    length = 100
    sorted_list = set()
    while len(sorted_list) < length:
        sorted_list.add(random.randint(-3*length, 3*length))
    sorted_list = sorted(list(sorted_list))

    start = time.time()
    for target in sorted_list:
        binary_search(sorted_list, target)
    end = time.time()
    print("Binary search time: ", (end - start)/length, "seconds")`

我很困惑，希望您能给我任何反馈。

如前所述，我通过将“if list[midpoint] == target:”交换为“if midpoint == target:”以及“elif target < list[midpoint]" for "elif target < midpoint". So far so good, no index error! But then when I was debugging and keeping track of "midpoint == target", whenever the midpoint was found, it began to increase the midpoint repeatedly which increased the expected time. I know that "print("Binary search time: ", (end - start)/length, "seconds")" should likely be around 6 with a list that is much larger (length = 1000) so it surprises me that a length of 100 gets around 3 on most of my tests (and my PC is not that slow).

”来“修复”了该问题

Answer 1

low

、

high

和

midpoint

是列表中的索引（位置编号），而不是列表的实际元素。这就是导致

IndexError

的原因，因为列表元素太大/太小而无法解释为索引。

所以

low = list[0]

和

high = list[-1]

将

low

和

high

设置为列表元素；要使它们成为索引，您可以设置

low = 0

，

high = len(list) - 1

。

此外，调用列表可能不是一个好主意

list

，因为这是列表类的默认Python名称（尽管它不会在此处引起问题，因为它在函数范围内）

import random

def binary_search(list, target, low=None, high=None):
    if low is None:
        low = 0 # Sets low to an index
    if high is None:
        high = len(list) - 1 # Sets high to an index
    midpoint = (low+high) // 2

    if high < low:
        return print("Target was not in the list")
    if list[midpoint] == target:
        return midpoint
    elif target < list[midpoint]:
        return binary_search(list, target, low, midpoint-1)
        # new max == midpoint-1 (because it was not the target)
    else:
        return binary_search(list, target, midpoint+1, high)
        # new min == midpoint+1 (because it was not the target)`

if __name__ == '__main__':
    # tests how fast the binary search is by randomly generating a sorted list
    length = 100
    sorted_list = set()
    while len(sorted_list) < length:
        sorted_list.add(random.randint(-3*length, 3*length))
    sorted_list = sorted(list(sorted_list))

    start = time.time()
    for target in sorted_list:
        binary_search(sorted_list, target)
    end = time.time()
    print("Binary search time: ", (end - start)/length, "seconds")

二分查找时间：6.914138793945312e-07秒