搜索是在一个项目集合中找到一个特定项目的算法过程。搜索通常的答案是真的或假的，因为该项目是否存在。
搜索的几种常见方法:
- 顺序查找
- 二分法查找
- 二叉树查找
- 哈希查找
二分查找又称折半查找，优点是：
- 比较次数少
- ，查找速度快，
- 平均性能好﹔
其缺点是：
- 要求待查表为有序表
- 插入删除困难
因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
2.2 二分法查找的步骤首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功;否则利用中间位置记录将表希成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
2.3 二分法查找的例子这里的二分法查找就和人查字典类似，首先翻到字典的一半位置( s t a r t + e n d 2 = 0 + 8 2 = 4 frac{start+end}{2} = frac{0+8}{2} = 4 2start+end=20+8=4)，看看此时的字母是多少：
- 如果我们要找的在该字母的前面，我们就将前面的对半分( s t a r t + e n d 2 = 0 + 3 2 = 1 frac{start+end}{2} = frac{0 + 3}{2} = 1 2start+end=20+3=1)；
- 如果我们要找的在该字母的后面，我们就将后面的对半分( s t a r t + e n d 2 = 2 + 3 2 = 2 frac{start+end}{2} = frac{2 + 3}{2} = 2 2start+end=22+3=2) -> 已经找到了！
- 依次执行，直到找到目标位置…
在二分的时候一定要明确起始的index和结束的index！
看图说话：
2.4 二分法查找的注意事项在二分的时候一定要明确起始的index和结束的index！
2.5 二分法查找的代码实现 2.5.1 递归实现在二分的时候一定要明确起始的index和结束的index！
# coding: utf-8
def binary_search(alist, target):
"""二分法查找
对于二分法查找的代码实现，最好的实现方式是使用递归
"""
n = len(alist)
if n > 0: # 递归的终止条件
mid = n // 2
if alist[mid] == target:
return True
elif target < alist[mid]: # 往左半部分查找
return binary_search(alist[:mid], target)
else: # 往右半部分查找
return binary_search(alist[mid + 1:],
target) # 注意alist[mid]这个数我们就不要了
else: # 说明没有该元素，则返回False
return False
if __name__ == "__main__":
ls = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(ls)
res_1 = binary_search(ls, target=26)
res_2 = binary_search(ls, target=100)
print(ls)
print(res_1)
print(res_2)
"""
[54, 26, 93, 17, 77, 31, 44, 55, 20]
[54, 26, 93, 17, 77, 31, 44, 55, 20]
True
False
"""
2.5.2 非递归的实现
# coding: utf-8
def binary_search(alist, target):
"""二分法查找(非递归版本)
对于非递归版本，只能在原有list上进行操作，必须涉及：
1. 起始位置下标
2. 结束位置下标
"""
n = len(alist)
first_idx = 0
last_idx = n - 1
while first_idx <= last_idx: # 一旦first_idx > last_idx时，表示已经越界，没有该数值，返回False
mid = (first_idx + last_idx) // 2
if alist[mid] == target:
return True
elif alist[mid] > target: # ←
# 改变起始位置和结束位置就可以改变搜索范围
last_idx = mid - 1 # 不要之前的mid了
else: # →
first_idx = mid + 1 # 不要之前的mid了
return False
if __name__ == "__main__":
ls = [54, 26, 93, 17, 77, 31, 44, 55, 20]
print(ls)
res_1 = binary_search(ls, target=26)
res_2 = binary_search(ls, target=100)
print(ls)
print(res_1)
print(res_2)
"""
[54, 26, 93, 17, 77, 31, 44, 55, 20]
[54, 26, 93, 17, 77, 31, 44, 55, 20]
True
False
"""
2.5.3 非递归版本和递归版本的区别
两种代码实现之间最大的区别就在于：
- 在写递归算法时，我们就用递归的思想去重新调用函数，但是使用递归在重新调用函数时会产生一个新的列表；
- 在非递归的实现中，我们不能调用函数自身了，因此需要重新划分查找的范围
def binary_search(alist, target):
if len(alist) == 0:
return False
else:
mid = len(alist) // 2
if alist[mid] == target:
return True
elif alist[mid] > target:
return binary_search(alist[:mid], target=target) # [: mid-1]
else:
return binary_search(alist[mid + 1:], target=target) # [mid+1: n]
2.6.2 非递归实现
def binary_search(alist, target):
first = 0
last = len(alist) - 1
while first <= last:
mid = (first + last) // 2
if alist[mid] == target:
return True
elif alist[mid] > target:
last = mid - 1 # 此时first不变
else:
first = mid + 1 # 此时last不变
return False
2.7 二分查找的时间复杂度
首先我们先考虑最坏时间复杂度。我们之前学习的希尔排序、归并排序和快排都会涉及到二分法，所以我们假设它一直需要二分，也就是 2 t = n 2^t = n 2t=n，即二分t次将整个数组分完，所以次数 t = log 2 n t = log_2^n t=log2n。
那么我们考虑一下它的最优时间复杂度，即第一次求得中间值就是目标值target，就不需要二分了，所以我们认为此时的时间复杂度为 O ( 1 ) O(1) O(1)。
- 最优时间复杂度： O ( 1 ) O(1) O(1)
- 最坏时间复杂度： O ( log 2 n ) O(log_2^n) O(log2n)
我们与之前从头到尾那样遍历去找元素的方法对比一下：
| 算法 | 最优时间复杂度 | 最坏时间复杂度 | 最优说明 |
|---|---|---|---|
| 遍历 | O ( 1 ) O(1) O(1) | O ( n ) O(n) O(n) | 第一个元素即为target |
| 二分查找 | O ( 1 ) O(1) O(1) | O ( log 2 n ) O(log_2^n) O(log2n) | 第一个中间的值就是target |
很明显， O ( log 2 n ) O(log_2^n) O(log2n)的时间复杂度明显比 O ( n ) O(n) O(n)要低的多。
