Python 二分查找

Question

我是一名初级程序员，我想在没有任何帮助的情况下从头开始制作我自己的二进制搜索算法。可以肯定地说它进展不顺利。我希望有人能在我的代码中找到错误。我修复了一些问题，但现在我已经运行解决了如果找不到大于中间索引的值的问题，并且一旦它达到不等于目标的单个值就不会结束。

    import random

userInput = 100
numbers = []

for i in range(100):
    numbers.append(random.randint(0, 100))

#Adding 100 to use as a test
numbers.append(100)
numbers.sort()
print(numbers)

def binarySearch(list, target):
    midIndex = int(len(list)/2)
    midValue = list[midIndex]

    if midValue == target:
        print("We found " + str(target))

    elif target > midValue:
        newList = numbers[midIndex:]
        binarySearch(newList, target)

    elif target < midValue:
        newList = numbers[:midIndex]
        binarySearch(newList, target)

    elif len(list) == 1 and list[0] != target:
        print(target + " is not in the list")

    else:
        print("It's not in the list")

binarySearch(numbers, userInput)

Answer 1

您的代码有两个主要问题：

mid 用于表示索引和值。
从未到达 binarySearch() 的结尾。

问题 #1：`mid`

使用 list 的切片创建 newList 时，您正在使用 mid 作为索引：

elif target > mid:
    newList = numbers[mid:]

但是，mid 不是索引。就是list:

中间的值

mid = list[int(len(list)/2)]

尝试使用两个变量：

midIndex = int(len(list)/2)
midValue = list[midIndex]

问题 #2：`binarySearch()`

binarySearch() 永远不会到达最后的 elif 看看 target 是否不在列表中。

只有在检查了以下条件后才能达到最终的elif：

if midValue == target:
    ...
elif target > midValue:
    ...
elif target < midValue:
    ...

显然，如果 midValue 和 target 是两个数字，这些比较之一必须 return True.

由于执行检查的顺序，binarySearch() 永远不会到达此部分：

elif len(list) == 1 and list[0] != target:
    ...

要解决此问题，请尝试重新排列您的 if 语句，以便 binarySearch() 到达代码的这一部分。

Python 二分查找

Python Binary Search

python

loops

binary-search

问题 #1：`mid`

问题 #2：`binarySearch()`

Python 二分查找

Python Binary Search

python

loops

binary-search

问题 #1：mid

问题 #2：binarySearch()

问题 #1：`mid`

问题 #2：`binarySearch()`