一、来源

来自《算法：C语言实现(第1-4部分)第3版》书的程序2.1和2.2。
书的第2章主要讲的是算法分析的原理，理论偏多，实例偏少，整章就只有这两个程序的片段。

二、两个版本的区别

程序功能：从已经排好序的数组中，找到指定值的下标。

2.1版本：顺序查找。依次遍历数组中的每个元素，如果找到了就返回。运气好的话第1次就找到了，运气不好的话第N次才能找到，平均需要找 N/2 次。

2.2版本：二分查找。由于数组已经排好序了，因此可以从中间找起，运气好的话第1次就找到了，没找到的话，目标数要么在数组的前半段，要么在数组的后半段，于是下次的搜索范围就缩小了一半，搜索量相比于顺序查找呈指数级下降，平均需要找 ( log ⁡ 2 N \log_2{N} log2​N)/2 次。

三、性能测试结果

注：从数组中找一个元素太快了，导致无法对比，因此本例中是随机生成了10万个值。

四、源码

源文件比较多，就不在文章里贴了，链接在这里：github、gitee

五、二分查找示意图

以下是从一组顺序的数中找出42的过程：

图片来源：https://algorithm-visualizer.org/branch-and-bound/binary-search

全文完