【程序员常用十算法】二分查找法—5分钟掌握

【上期《ChatGPT写的vs我写的——快速排序算法》出来以后，有不少朋友都在感慨未来怎么办啊，是不是初级程序员这些岗位都可以被取代了？我觉得这是一体两面，可以理解为危机（被取代）、也可以理解为机遇（解放生产力），但不论如何这些其实都并不应该影响你持续学习的决策与行动，相反只有在某一领域持续深耕下去，才更有储备去打破一些东西】

给我5分钟，讲明白二分查找法——

一、算法原理：

二分查找，也叫折半查找，是一种适用于顺序存储结构的查找方法。它是一种效率较高的查找方法，时间复杂度为 O(lgn)，但它需要注意：它仅能用于有序表中。也就是说，表中的元素需按关键字大小有序排列。

假设有如下一本1000页的书，给定一个页码，如何快速地找到它呢？如果一页一页逐步查找，最高是不是可能要999次？但用二分法，就可以把查找的次数降到个位数。

第一步：找到1~1000的中位数，通过索引去找，索引是从0开始的，所以这里就是（0+999）//2=499，对应数值为500。即：

第二步：给定一个想要查找的页码比如365，将365与中位数500进行比较，因365<500，则锁定左区：

第三步：求左区的中位数，方法与第一步相同，求得索引为249，对应数值为250。即：

第四步：将365与250比较，因365>250，则锁定右区：

依次类推，最终找到页码365，找到的意思就是找到页码365对应的索引364，这个例子里数列是1~1000，每次增加1，可能有些同学会感觉这还需要找吗，都可以直接看出来了。

但想象一下，实际碰到的数列不一定是等比或等差，这时候就得有一种算法快速地能定位想找的这个数的位置（即索引），通过直观去看是看不出来的。

二、Python代码实现

看懂了算法的原理介绍，代码就是算法的具现：

这段算法每个语句都加上了注释，应该很容易读懂。这里查找到第9次，就找到了365对应的索引。具体运行结果为：

此外，我们可以察觉到算法的原理实际上是一个递归的过程，因为代码也可以用递归来实现：

运行结果相同，具体为：

【今天就讲到这里，每天进步一点点】