[Python知识库]python实现二分查找

python实现二分查找

1. 函数binary_search接收一个有序数据和一个元素。如果指定的元素包含在数组中，这个函数将返回其位置。
2. 仅当列表是有序列表的时候，二分查找才管用`

import random
#导入random模块

def binary_search(list,item):
    low = 0
    high = len(list) - 1
    #low和high用于跟踪要在其中查找的列表部分
    while low <= high:
    #只要范围没有缩小到只包含一个元素，就检查中间的元素
        mid = (low + high) // 2
        #每次都检查中间的元素
        #如果（low+high）不是偶数，python将向下取整
        guess = list[mid]
        #猜的元素
        if guess == item:
        #找到了元素
            return mid
        elif guess > item:
        #猜的数字大了
            high = mid - 1
        else:
        #猜的数字小了
            low = mid + 1
    return None #没有指定的元素

# my_list = [1,3,5,7,9]
my_list = list(range(128))
#输出有序列表
print(my_list)
print(binary_search(my_list,5))
#别忘了索引从0开始