1. 二分查找的原理
对于已经排序的列表进行最快速度的查找
2. 代码实现
(1) 递归实现
- def binary_search(alist, item):
- if len(alist) == 0:
- return False
- else:
- midpoint = len(alist)//2
- if alist[midpoint]==item:
- return True
- else:
- if item<alist[midpoint]:
- return binary_search(alist[:midpoint],item)
- else:
- return binary_search(alist[midpoint+1:],item)
- testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
- print(binary_search(testlist, 3))
- print(binary_search(testlist, 13))
(2) 非递归实现
- def binary_search(alist, item):
- first = 0
- last = len(alist)-1
- while first<=last:
- midpoint = (first + last)/2
- if alist[midpoint] == item:
- return True
- elif item < alist[midpoint]:
- last = midpoint-1
- else:
- first = midpoint+1
- return False
- testlist = [0, 1, 2, 8, 13, 17, 19, 32, 42,]
- print(binary_search(testlist, 3))
- print(binary_search(testlist, 13))
3. 时间复杂度
最优时间复杂度: O(1)
最坏时间复杂度: O(logn)
因为是二分所有分多少次代表要查多少次, 即为 logn
来源: http://www.bubuko.com/infodetail-2724516.html