查找问题是计算机中需要解决的一个非常普遍、重要而且基础的问题。比如：你去银行办理业务，柜员要输入你的身份证号，这就是一个查找的过程，再比如，百度中的搜索，你输入一个关键词，这也是一个查找的过程。那计算机中一般是如何解决这类查找问题的呢？最基础的一种方法就是二分查找法。

使用二分查找法有一个前提，那就是待查找的数列必须是一个有序数列。这也从另一个角度说明，我们之前说了那么多排序算法，其实排序算法很多情况下是解决问题算法中的一个子算法，这是因为，排好序是基础。

二分查找法的描述

从算法描述来看，二次查找法确实是很简单，而且思路很容易理解，但对于二分查找法，还是有很多故事和要注意的问题的，下面我就一一给您说道说道。

二分查找法的“千年虫”问题

在说这个问题之前，我们先看二分查找法的核心源码。

二分查找法的源码

二次查找法的思想1946年就提出来了，为什么用了16年，才出现第一个没有bug的方法。在这个源码中，有一个非常不起眼的语句是：int mid = (l+r)/2;这个语句您举得有问题吗？理论上来说是有问题的，因为当l和r都非常大的时候，相加是会越界的。而那个时候，计算机的硬件还非常落后，所以才导致了这个问题。这个问题也非常的好改，我们只要改成：int mid = l + (r - l)/2;就可以了。

递归实现二分查找法

通过上面的源码我们可以很轻易的看出来，二分查找法有非常强的递归特性，那我们该如何用递归来实现二分查找法呢，用递归有什么好处呢？请看源码：

递归实现二分查找法的源码

递归的方法实现二分查找，确实是很简单，把上面while循环中的结束条件作为递归结束的条件，稍加改造就可以（当然这需要你真正理解递归的过程）。递归算法实现二分查找有两个特点：

1）递归的算法逻辑非常简单；

2）递归的算法性能更低一些，但和非递归实现方式的性能差异也只是常熟级别的。

floor和ceil如何实现

当数据中有很多重复元素的时候，我们会有一些这样的需求，比如：

1）找到重复元素的开始位置和结束位置；

2）当被查找的元素不存在时，能不能返回和这个元素相邻两个元素的位置；

对于这个问题，有两个函数在大部分的算法中其实有已经实现了，那就是floor和ceil。那这两个函数的定义是什么呢？请看下图：

floor和ceil的定义

再此我给您留一个作业题，即希望您能写出floor和ceil函数的代码实现。如果您真的能够写出代码实现，相信您对二分查找法就已经可以说是彻底理解了。

我是徐建航，这是我写的第69篇文章，欢迎你加入007社群，七天写一篇，一起写七年，七年之后一起去南极。