如何实现二分查找？

Question

我正在尝试创建一个二进制搜索功能，我已经尝试使用下面的代码，但我是 python 的初学者；我在 i == alist[i] 行收到错误 "list indices must be integers, not str"。你能帮我解决这个问题吗？这是完整的代码：

def bsort(alist, i):
    left = 0
    right = len(alist)-1
    i == alist[i]

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

    if alist[mid] < i :
        left = [mid] + 1

    elif alis[mid] > i :
        right = [mid] + 1

    elif alist[mid] == i :
        print ("word found at", i )

    elif left > right:
        print ("Not Found!")       


i = input("Enter a search >")
alist = ["rat","cat","bat","sat","spat"]
bsort(alist, i)

Answer 1

首先是==，它检查相等性并且不赋值。使用单个 = 而不是 == 进行赋值。

此外，您的方法将 i 作为字符串，然后使用字符串来引用列表的索引。这会产生错误。

您正在使用二进制搜索的整数方法来查找不正确的字符串。特别是因为您的字符串既不按长度排序，也不按字母顺序排序。参考其他一些方法来实现。

见Binary string search in Python 3.x

Answer 2

你得到 'list indices must be integers, not str' 因为你在列表中将字符串作为二进制搜索的输入，并在第 4 行中将其用作列表的索引，这导致了错误，因为列表是通过索引的整数。

另一个问题： 1. 在应用二进制搜索之前必须对您的列表进行排序， 2.line 6 导致另一个错误，因为 int 对象不可迭代。 3.and 为了在列表中进行完整搜索，您必须包含一个 while 循环，它将检测您的前两个 if 条件并帮助循环列表。

这段代码可能会对您有所帮助：

def bsort(alist,blist,i):

left = 0
right = len(alist)-1

mid = (left + right)//2

while left <= right:    #  loop through the list
    if alist[mid] < i :
        left = mid + 1
    elif alist[mid] > i :
        right = mid + 1
    elif alist[mid] == i :
        print ("word found at", blist.index(i) )    # will print the original index of element i.e. before sorting
        exit()     #to stop through infinite looping
    elif left > right:
        print ("Not Found!")

i = input("Enter a search >") #你要搜索的字符串 alist = ["rat","cat","bat","sat","spat"] blist = alist[:] # 创建另一个列表以了解原始列表中的元素索引 alist.sort() # 排序列表进行二分查找 bsort(alist,blist,i)

Answer 3

因此，根据您的问题，您正在尝试让二进制 search 为您的示例工作。首先，知道二分搜索仅对 排序的 数据可靠地工作是很有用的。这与标准的线性搜索完全不同，后者总是会找到值，而不管顺序如何。正如您可能已经知道的那样，二分搜索是首选，因为它在每次迭代中消除了一半的潜在候选者，而线性搜索仅消除了一个元素。话虽如此，让我们讨论一下我对您的程序所做的修改。首先，一些外观上的改变可以大大增加程序的清晰度。

1.) 使用描述性的变量名非常重要，可以为阅读您的代码的其他人提供注释，了解变量的内容和功能。这在像 python 这样的语言中尤为重要，在这种语言中，仅通过阅读代码无法轻易推断出变量类型。因此，我没有多次重复使用变量 i，而是将您的函数参数重命名为 target，因为这是我们试图定位的搜索词，即我们的 'target'。我还将您的函数从 'bsort' 重命名为 'bsearch' ，这意味着该函数对某些东西进行排序，更合适的名称是 'bsearch' 因为它更准确地描述了函数的作用。

2.) 可以使用循环或递归来实现二进制搜索。为简单起见，我选择了使用循环的迭代路线。正如我之前提到的，二分搜索通过每次迭代消除一半的潜在搜索候选者来工作。如果没有循环，您确实会排除一半的候选人（只有一次），但除非您非常幸运，否则您很可能找不到您正在搜索的术语！相反，您需要继续此过程，直到找到要搜索的术语。这是while True:循环的功能。

3.) 最后，我们确保使用整数来访问列表的索引。 python 中的所有列表都是从 0 to n-1 索引的，其中 n 是列表中元素的数量。我们不能使用诸如 2.5 之类的浮点值访问列表，因为它不对应于列表中的任何特定 'slot'。同样，我们不能使用字符串来访问我们的元素，因为列表再次需要整数来执行查找。这就是 mid = int((left + right)/2).

的目的

综上所述，这应该可以达到您的预期目的。我希望这可以帮助你！我还鼓励您看一些如何实现二进制搜索的示例，例如 this one.

def bsearch(alist, target):
    left = 0
    right = len(alist)-1

    while True:
        mid = int((left + right)/2)
        if alist[mid] < target :
            left = mid + 1
        elif alist[mid] > target :
            right = mid + 1
        elif alist[mid] == target :
            print ("word '" + target + "' found at " + str(mid))
            break
        elif left > right:
            print ("Not Found!")
            break       


i = input("Enter a search >")
alist = ["rat","cat","bat","sat","spat"]
alist.sort()
bsearch(alist, i)

如何实现二分查找？

How to implement a binary search?

python

sorting

algorithm

binary-search

python-3.x