二分查找
对于有序表，我们有一种比顺序查找更加优秀的查找算法。那就是二分查找算法。
假设有一个从小到大排序的列表。我们从列表中间的项进行对比，如果匹配查找项，则查找结束；如果不匹配，那么就有两种情况：
-
列表中间项比查找项大，那么查找项只可能出现在前半部分；
-
列表中间项比查找项小，那么查找项只可能出现在后半部分。
但无论如何，我们都要将比对范围缩小到原来的一半：n/2。
然后继续采用上述方法进行查找，查找范围变为列表的前半部分或后半部分，继续查找……。直到找到目标数据项或者不能再继续缩小范围为止。
1. python代码实现
def binary_search(a_list, item):
"""
二分查找
:param a_list: 被查找列表
:param item: 目标元素
:returns: 元素是否在列表中被找到
"""
first = 0
last = len(a_list) - 1
while first <= last:
midpoint = (first + last) // 2
if a_list[midpoint] == item:
return True
elif a_list[midpoint] > item:
last = midpoint - 1
else:
first = midpoint + 1
return False
2. 递归算法实现
二分查找算法实际上体现了解决问题的典型策略：分而治之。
将问题分为若干更小规模的部分通过解决每一个小规模部分问题，并将结果汇总得到原问题的解。
因此，二分法也适合用递归算法来实现（因为递归算法也是一种典型的分治策略算法）：
def binary_search(a_list, item):
"""
二分查找
:param a_list: 被查找列表
:param item: 目标元素
:returns: 元素是否在列表中被找到
"""
list_size = len(a_list)
if len(a_list) == 0:
return False
else:
midpoint = list_size // 2
if a_list[midpoint] == item:
return True
elif a_list[midpoint] > item:
return binary_search(a_list[0:midpoint], item)
else:
return binary_search(a_list[midpoint + 1 :], item)
3. 算法分析
由于二分查找，每次比对都将下一步的比对范围缩小一半。所以，每次比对后剩余数据项如下表所示：
| 对比 | 剩余的元素数量 |
|---|
| 1 |
n
/
2
n/2
n/2 | | 2 |
n
/
4
n/4
n/4 | | 3 |
n
/
8
n/8
n/8 | | … | … | |
i
\text i
i |
n
/
2
i
n/2^i
n/2i |
当比对次数足够多以后，比对范围内就会仅剩余1个数据项。无论这个数据项是否匹配查找项，比对最终都会结束，接下列方程：
n
2
i
=
1
\frac {n}{2^i}=1
2in?=1得到：
i
=
log
?
2
(
n
)
i=\log_2(n)
i=log2?(n)，所以二分查找算法的复杂度是
O
(
log
?
n
)
O(\log n)
O(logn)。
4. 二分查找的进一步思考
在递归算法实现的二分查找算法中除了比对，还有一个因素需要
注意到：切片操作。这一操作的算法复杂度是
O
(
k
)
O(k)
O(k)，这使得整个算法的复杂度稍有增加。但这仅仅是为了可读性更好，它完全可以通过传入首尾端索引的方式来代替。
另外，虽然二分查找在时间复杂度上优于顺序查找。但也要考虑到对数据项进行排序的开销：
- 如果一次排序后，可以进行多次查找，那么排序的开销就可以忽略。
- 如果数据集经常变动，排序完成后查找不了几次，那么还是直接用无序表加上顺序查找来得经济。
所以，在算法选择的问题上，光看时间复杂度的优劣是不够的，还需要考虑到实际应用的情况。
|