Python实现二分查找

二分查找又叫作折半查找，意思为每次查找后，查找的范围都折半。这样查找到最后，查找范围内只剩一个数时，判断它是否为要查找的数。如果是，就记录它的位置；如果不是，则要查找的数不在这个数组中。

用程序实现一个有 15 个元素的数组 [1,3,5,6,7,8,13,14,15,17,18,24,30,43,56] 的二分查找。

分析：二分查找需要两个指针，一个指向数组的第一个元素，叫做头指针；另一个指向数组最后一个元素的后方，叫作尾指针。

在程序验证过程中，发现可以直接把头指针置为 -1，循环条件为 (tail-head)>1，不成立时可以分三种情况：

• 开头处——tail-(-1) = 1，tail为0，表示下标0处已经判断过
• 结尾处——len(numbers)-head = 1，head=len(numbers)-1，表示最后一个元素被判断过
• 中间——tail-head = 1，tail和head表示的下标被判断过

完整程序如下

numbers = [1, 3, 5, 6, 7, 8, 13, 14, 15, 17, 18, 24, 30, 43, 56]

head = -1
tail = len(numbers)
number = int(input('请输入要查找的数字：'))

while (tail-head) > 1:
    mid = (tail+head) // 2
    if numbers[mid] == number:
        print(f'下标是{mid}')
        break
    elif numbers[mid] > number:
        tail = mid
    else:
        head = mid
else:
    print(f'{number}不在列表中')