代码之家 › 专栏 › 技术社区 › Laveen

python中的二进制搜索程序不会停止循环

binary-search python-3.x algorithm python

Laveen · 技术社区 · 7 年前

如果提供了给定的值,我将尝试对列表/数组进行二进制搜索。这是我的代码:

item = "dog"
list = ["banana","dog","apple","britain","light","error","brother"]
length = len(list)
guess = (length + 1) // 2
counter = 0
while list[guess] != item:
    counter = counter + 1
    print("False")
    if guess < list.index(item):
        for i in range(guess):
            del list[i]
    else:
        largest = list[-1]
        for i in range(guess, list.index(largest)):
            del list[i]
    length = len(list)
    guess = (length + 1) // 2
print(f"I found {list[guess]} and it took {counter} tries.")

我希望它在我的列表中对单词“dog”进行二进制搜索,但它陷入了困境,只会不断循环并打印false。我不知道为什么。

如果有人能更正我的代码并告诉我出了什么问题,我们将不胜感激。

1 回复 | 直到 7 年前

Jose A. García 7 年前

我写了一个函数来做二进制搜索,我只想回答这个问题,但现在我想最好告诉你应该如何进行二进制搜索。

允许 my_list = [2, 4, 1, 6, 3, 5] 和我们的商品 5 . 为了进行二进制搜索,我们首先需要对列表进行排序,所以在我们的例子中 my_list = [1, 2, 3, 4, 5, 6] .

你需要跟踪两个位置,我们称之为 lo 和 hi lo = 0 和 hi = len(my_list) - 1

[1, 2, 3, 4, 5, 6]
 l              h
 0              5

然后我们计算两者的中间值为 mid = (hi+lo) // 2 在这种情况下 mid = 2 . ( a//b 与相同 math.floor(a/b) )

我们现在比较项目( )与 my_list[mid] ( 3 )我们的项目更大,所以我们知道项目的位置必须高于 mid 所以我们可以这么说 lo = mid + 1

[1, 2, 3, 4, 5, 6]
          l     h
          3     5

mid = (lo + hi // 2) 和 mid = 4 my_列表[mid] ( 5. )带项目( 5. )我们可以知道这个项目的索引是 中间 .

这个解释很模糊,你必须考虑一下是否应该这样做 lo=中间+1 lo = mid ,当项目低于mid时会发生什么,当项目不在列表中时会发生什么。但既然你在研究这个,我就让你想想。

希望有帮助!

推荐文章

Aaron Green · 我的python程序无法识别数据库的存在,即使它在那里

1 年前

danial · 如何在多个字符串的每个位置找到最频繁的字符

2 年前

Henry · 使用Python将json重新格式化为键值对

2 年前

eymentakak · json字典类型错误:字符串索引必须是整数

2 年前

Qubix · 从熊猫数据帧创建相对熵矩阵

2 年前

FÄÅ ÛÅ · 字典、列表和字符串

2 年前

OrbitDuster · 如何使用gmail api在python中打印gmail正文?

2 年前

guiguilecodeur · 如何删除我的词汇表中的重复元素

2 年前

Susheel P M · 这是关于if-else语句[关闭]

2 年前

Slartibartfast · 关于Python版本安装

2 年前