Python中的二分查找（折半查找）

1.题目要求

在一个有序的列表中，寻找我们搜索值得索引，如果列表中有搜索值，返回索引，没有搜索的值返回None；

2.基本思想

（这里假设数组元素呈升序排列）将n个元素分成个数大致相同的两半，取a[n/2]与欲查找的x作比较，如果x=a[n/2]则找到x，算法终止；如果xa[n/2]，则我们只要在数组a的右 半部继续搜索x。

3.时间复杂度

4.代码实现

def binary_search(arr, search):
    low, high = 0, len(arr) - 1  # 第一次将最极端的两个索引记下来
    while low