二分查找算法+Python代码

1二分查找算法

二分查找是一种算法，其输入是一个有序的元素列表。如果要查找的元素包含在列表中，二分查找返回其位置；否则返回null。

下面的实例说明了二分查找的工作原理。我随便想一个1～100的数字，目标是你以最小的次数猜到这个数字。你每次猜测后，我会说小了、大了或对了。

假设你从你开始一次往上猜测，过程会是这样的。

这是简单查找，更准确的说法是傻找。每次猜测都只能排除一个数字。如果我的数字是99，你得猜99次才能猜到。

最佳的查找方式，从50开始。

小了，但排除了一半的数字！你知道1～50都小了。接下来，你猜75.

大了，，那余下的数字又排除了一半！使用二分法查找时，你猜测的是中间的数字，从而每次都将余下的数字排除一半。接下来，你猜63(50-75中间的数字)。

这就是二分法查找。每次猜测排除的数字个数如下。不管我心里想的那个数字，你在7次之内都能猜到，因为每次猜测都将排除很多数字！

假设你要在字典中查找一个单词，而该字典包含240000和单词，你认为每种查找最多需求多少步？

如果要查找的单词位于字典末尾，使用简单查找将需要240000步。使用二分查找时，每次排除一半单词，直到最后剩下一个单词。一般而言，对于包含n个元素的列表，用二分法查找最多需步，而简单查找最多需要n步。仅当列表有序的时候二分法才管用。

2 Python代码

def binary_search(orderly_list, number):
    print(orderly_list)
    if len(orderly_list) == 0:
        print('not exist')  # 每次查找后的剩余部分
        return
    mid_index = len(orderly_list) // 2  # 向下取整
    if number > orderly_list[mid_index]:  # 要查找的数字小于列表中间值
        binary_search(orderly_list[mid_index + 1:], number)  # 列表折半继续往右找
    elif number < orderly_list[mid_index]:  # 要查找的数字大于列表中间
        binary_search(orderly_list[0:mid_index], number)  # 列表折半继续往左找
    else:
        print('find exist')
        # print(orderly_list.index(number))


number_list = [1, 3, 5, 7, 9, 11, 12, 15, 16]  # 定义一个列表
binary_search(number_list, N)