二分查找法

1. 理论基础

当我们要从一个序列中查找一个元素的时候，最快想到的方法就是顺序查找法，但这种方法仅仅是暴力的把每个元素都排查一遍，元素个数少的时候还可以，一旦元素个数很多，效率就会非常低下。

二分查找算法也叫折半查找算法。该算法要求数组数据要采用顺序存储有序排列，每次通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素。

（1）查找的序列必须是有序的。有序是指所有元素是按照升序或降序排列好的，元素与元素之间的差值是随机的。

（2）查找的元素只能是一个，不能实现多值查找。

先找到有序序列的中间元素mid，然后拿它跟要找的目标元素进行对比，就可以初步判断目标元素的所在范围，既然查找范围已经确定，则该范围之外的元素就可以不用找了。按照上面的步骤反复查找下去直到找到目标元素为止。

二分查找每一次查找都可以缩减一半的查找范围，则其时间复杂度为 $\log_2 N$ .

举例：若共有2^32个元素，则采用二分查找最多32次就可以找到目标，但是采用顺序查找的方法最多需要查找4294967296次。

2 编程实现

写在最后：文章是在学习过程中做的学习笔记，同时与志同道合者分享，文章内容均经过我自己实验证实可行，如有问题欢迎留言，很高兴一起交流讨论，共同进步！

最后编辑于：2022.12.16 10:25:59

©著作权归作者所有,转载或内容合作请联系作者
【社区内容提示】社区部分内容疑似由AI辅助生成，浏览时请结合常识与多方信息审慎甄别。
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。