现有一个问题：
给一个列表,以及一个元素，返回: 元素的下表或未查找到元素
从列表第一个元素开始，顺序进行搜索，直到找到为止。
时间复杂度：O(n)
从有序列表的候选区data[0:n]开始，通过对待查找的值与候选区中间值的比较，可以使候选区减少一半。
示例：列表[1,2,3,4,5,6,7,8,9]，使用二分查找来查找3
图一: 待查找值3与中间值mid比较
图二: 候选区减少一半
图三: 再次比较
图四: 候选区再次减少一半
图五: 最后要么找到,要么没有
循环版本：
善用low high mid mid+1 mid-1 ，比切片好, 时间度O(n)
li = list(range(10)) def foo(li, arg): # 时间复杂度: O(logn) low = 0 high = len(li) - 1 # high/low是索引(下标) while low <= high: mid = (high + low) // 2 if arg < li[mid]: high = mid - 1 elif arg > li[mid]: low = mid + 1 else: return mid return None print(foo(li, 3)) # 3
递归版本：
def binary_search(lst, arg, low, high): if low <= high: mid = (low + high) // 2 if arg > lst[mid]: return binary_search(lst, arg, mid + 1, high) elif arg < lst[mid]: return binary_search(lst, arg, low, mid - 1) else: return mid else: return None li = list(range(10)) print(binary_search(li, 3, 0, len(li) - 1))
时间复杂度: O(logn)
原文：https://www.cnblogs.com/zhzhlong/p/12891152.html