为什么当元素不在列表中时我的二进制搜索功能不会停止？

Question

我有如下二分查找功能：

def in_bisect(sorted_list, target):

    temp = sorted_list[:]
    low = 0 
    mid = (len(temp)-1) // 2 
    high = len(temp)-1 
    count = 0
    
    if target > temp[high] or target < temp[low]:
        return False
    
    while True:
        mid = len(temp) // 2 
        count += 1
        if target == temp[mid]:
            print("Target found in %d steps " % count)
            return True

        elif target > temp[mid]:  
            low = mid             
            temp = temp[low:]
        
        elif target < temp[mid]: 
            high = mid           
            temp = temp[:high]

    
    return False

当我在给定的单词列表中查找元素时，它工作正常。但是，当我测试一个不在列表中的单词时，循环会进入无限期！！！

我已经用 113k+ 按字母顺序排序的单词列表对其进行了测试，它非常有效（或者至少我想的那样）它最多可以在 17 个步骤中找到目标。

这是我做的测试:

if __name__ == '__main__':
    fin = open('words.txt')
    a = []
    for line in fin:
        a.append(line.strip())
    print(in_bisect(a,'longsome'))

'longsome' 是 words.txt 文件中的一个词，如果我将其更改为 'blahblah' 循环将永远进行下去。

如果没有匹配项，我希望它立即 return False。另外，在此过程中提出任何改进建议，我们将不胜感激。

Answer 1

while 循环没有办法中断，所以直到我们运行超出搜索范围，我们继续，否则，我们中断。此外，low = mid + 1 是必需的，否则列表大小将无法正确减小。 high.

相同

def in_bisect(sorted_list, target):

    temp = sorted_list[:]
    low = 0 
    mid = (len(temp)-1) // 2 
    high = len(temp)-1 
    count = 0
    
    if target > temp[high] or target < temp[low]:
        return False
    
    while True:
        if len (temp) == 0:
            break
        mid = len(temp) // 2
        count += 1
        if target == temp[mid]:
            print("Target found in %d steps " % count)
            return True

        elif target > temp[mid]:  
            low = mid + 1             
            temp = temp[low:]
        
        elif target < temp[mid]: 
            high = mid - 1           
            temp = temp[:high + 1]

    
    return False

为什么当元素不在列表中时我的二进制搜索功能不会停止？

Why my binary search function doesn't stop when the element isn't in the list?

python

binary-search