二分查找

• 仅当列表是有序时，二分查找才能正常进行。
• 一般而言，对于包含n个元素的列表，用二分查找最多需要log2(n)步，而简单的查找最多需要n步。
• 设计二分查找函数时，其是由两个参数组成，一个是有序数组，另外一个是需要查找那个元素。

python3代码实现：

#定义二分查找函数
def binary_search(list, item):
    low = 0
    high = len(list) - 1

    while low <= high:
        mid = (low + high) // 2
        guess = list[mid]
        if guess == item:
            return mid
        if guess > item:
            high = mid -1
        else:
            low = mid + 1
    return None
#测试数组列表
my_list = [1, 3, 5, 7, 9, 10, 12, 14, 16, 17, 19, 21, 24, 26, 39, 72, 108, 128, 193]
#打印输出结果
print(binary_search(my_list, 10))  #10在第5位
print(binary_search(my_list, -1))  #-1不在元素列表中
print(binary_search(my_list, 39))  #39在列表第14位

pycharm测试结果：

C++实现：（待更新）