【小算法】二分查找
谈论算法，典型的问题除了排序，还有查找。
查找就是，从一个数据集合中查找某个数，如果找到了就返回该数据在数据集中的索引，否则返回 -1。
最简单的方法就是从头到尾依次查找。
但这有个问题，顺序查找时间复杂度是O(n)O(n)O(n)，如果要从 1 亿个数据中查找某个数，最坏的情况要查找 1 亿次。
那么有没有更快速的算法呢？
答案是有的，这篇文章讲的二分查找就是这样一种，它的时间复杂度是O(logn)O(log_{n})O(logn) 。
猜数字
我们小时候都玩过这样的游戏。
对方在心里默念一个数字。
然后，叫你猜。
你说： 42.
他说： 小了。
你说： 78
他说： 大了
你说： 64
他说： 小了
你说： 70
他微笑不语。
实际上，二分查找的逻辑和这个无异。
算法图例
假如要从下面的有序数组中查找 25 。
arr = [1,3,16,23,25,32,79]二分查找的思路就是每一次都和数组中的中间数据比较，不断缩小候选数据集的范围
在这里插入图片描述
上面的图例清晰明了。
因为每次查找都缩减了范围，所以数据集会折半。
折半的概念用数学符号表示就是lognlog_{n}logn,当然是以 2 对底数。
Python 代码
def binary_search(arr,value):
result = -1
low = 0
high = arr.__len__()
while low <= high:
middle = int ((high - low)/2) + low
if arr[middle] == value:
return middle
elif arr[middle] < value:
# searching in right sub list
low = middle + 1
elif arr[middle] > value:
# searching in left sub list
high = middle - 1
return result
if __name__ == "__main__":
arr = [1,3,16,23,25,32,79]
print("=======================")
print(arr)
result = binary_search(arr,25)
print("=======================")
print(result)
result = binary_search(arr,16)
print("=======================")
print(result)
result = binary_search(arr,15)
print("=======================")
print(result)代码结果：
=======================
[1, 3, 16, 23, 25, 32, 79]
=======================
4
=======================
2
=======================
-1代码比较简单，核心就是控制 low 和 high 两个游标不停地缩小选择范围。
如果什么都没有找到就返回 -1.
值得注意的是，二分查找法适用与有序数组。如果是无序的就不能操作。并且如果数据用链表形式也比较麻烦。
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2019/09/04 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
