《算法图解》日志一（python）（二分查找法）

二分查找

二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列.(摘自算法导论)

更佳的查找方法

现在我们来玩一个猜数的游戏，假设有一个人要我们猜0-99之间的一个数。那么最好的方法就是从0-99的中间数49开始猜。如果要猜的数小于49，就猜24（0-48的中间数）；如果要猜的数大于49，就猜74（50-99的中间数）。重复这个过程来缩小猜测的范围，直到猜出正确的数字。二分查找的工作方法就类似于此.

说明

1、我们会经常谈到log(对数)时间,因此你必须明白对数的概念,哔哩哔哩就有个视频是介绍对数的(课程⬅点击,免费)
2、在列表是有序的时候,二分查找才是管用的,例如电话谱就是有序的,那如果是无序的会怎么样呢?

知识站点

本系列使用大0表示法(下一章介绍)讨论运行时间时，log
指的都是log2。使用简单查找法查找元素时，在最糟情况下
需要查看每个元素。因此，如果列表包含8个数字，你最多
需要检查8个数字。而使用二分查找时， 最多需要检查log n
个元素。如果列表包含8个元素，你最多需要检查3个元
素，因为log8=3 (23= 8)。如果列表包含1024个元素，
你最多需要检查10个元素，因为log 1024 = 10 (21
=1024)，

对数

对数（logarithm）是对求幂的逆运算，一个数字的对数是必须产生另一个固定数字（基数）的指数。对数的符号log出自拉丁文logarithm，最早由意大利数学家卡瓦列里（Cavalieri）所使用。如果a的x次方等于N(a>0，且a不等于1)，那么数x叫做以a为底N的对数，记作x=logaN。其中，a叫做对数的底数，N叫做真数

示例代码

def bin_search(data_list, val):    
    low = 0                         # 最小数下标    
    high = len(data_list) - 1       # 最大数下标    
    while low <= high:        
        mid = (low + high) // 2     # 中间数下标        
        if data_list[mid] == val:   # 如果中间数下标等于val, 返回            
            return mid        
        elif data_list[mid] > val:  # 如果val在中间数左边, 移动high下标            
            high = mid - 1        
        else:                       # 如果val在中间数右边, 移动low下标            
            low = mid + 1    
    return # val不存在, 返回None
ret = bin_search(list(range(1, 10)), 3)
print(ret)