文章插图
1
二分法可以说是鼎鼎大名，哪怕是没有学过编程的同学，也许说不上来二分法这个名字，但是对于其中的精髓应该都是有所了解的 。不了解的同学也没关系，我一句话就能交代清楚：我们每次将一个集合一分为二，每次舍弃其中一半 。
早在两千多年前，庄子就搞清楚了二分法的精髓，他说：一尺之棰，日取其半，万世不竭 。从这个角度来说，二分法可能是这个世界上最古老的算法之一了 。
【算法浅谈——人人皆知却很多人写不对的二分法】
二分法不仅古老，而且在计算机系统当中非常常见，许多系统当中都用到了二分法的思想 。除此之外，在面试的时候，二分法的算法题也是常客 。因为二分法本身不复杂，几乎人人都会，但是对二分法的使用能力却各有不同 。出二分法的题，可以真实考察面试者的算法能力和编程功底 。
不说比较困难的算法题想不出思路，就说最简单没有任何难度的纯二分，在面试的时候，出错的写出bug的也大有人在 。
很多人会觉得奇怪，二分法这么简单的算法，真的有人写不出来吗？
还真的有，原因也很简单，恰恰就是二分法太简单了 。
无论是在算法导论还是在一些其他的算法教材当中，关于二分法的描述都不多，详细的会有一些图例展示一下二分法的思想，简单的就用几句话描述一下原理，最后再展示一下代码，就完事了 。读者在学的时候也是一样，看了一眼原理，哦，非常简单，再看一眼代码，只有三四行，差不多一眼就能记住，那就丢在一边吧 。到了真正上手的时候，问题一下就暴露了出来 。
文章插图
二分法最常见的问题有两个，一个是二分的区间边界不清楚，另一个是二分查找的结果不明确 。我想，这两个问题是前几次实现二分法的时候，一定会遇到的 。遗憾的是，目前的教材当中对于这两个问题介绍都不多，都只有代码，留给读者自行揣摩 。
2
我们先说第一个问题——边界
早在小学我们就学过，用l表示区间左边界，r表示区间右边界，mid=(l + r) / 2表示二分的中间点 。这个在数学里非常明确，但在编程的时候，有一个隐藏的问题被忽略了 。究竟这个区间是闭区间呢，还是开区间呢，还是半开半闭区间或者是半闭半开区间？如果这个问题不想清楚，想要一次性写出没有bug的代码，老实说很不容易 。
首先，二分终止的条件究竟怎么写，是while (l < r) 还是 while (l <= r) 还是别的？还有，在搜索的时候，我们究竟要不要将a[mid] == v的情况单独判断？我们是判断a[mid] < v还是a[mid] <= v？假设我们选择用a[mid] <= v，得到的结果为true 。我们知道答案应该在区间的右半边，我们需要舍弃左边的区间 。应该对l赋值，但是我们是赋值成l = m呢还是l=m + 1呢？又是为什么呢？
你看，如果l和r表示的区间不考虑清楚，我们在实际写代码的时候就会遇到这样棘手的问题 。坑爹的是，当我们为这些边界头疼的时候，我们并不能意识到这是因为我们没有搞清楚表示区间的方法导致的 。往往会觉得是自己不够熟悉 。
显然，要解决这个问题需要确定l和r表示的区间种类 。那么到底应该选择什么区间呢？是左闭右开，还是全闭，还是左开右闭呢？
答案有点出人意料，都行 。
理论上来说，不论选什么样的区间，只要代码得当，都是可以的，可以说是完全看个人喜好 。不过我个人推荐左闭右开，原因很简单，这个和编程当中的数组定义的情况一致 。我们都知道，在代码的世界里，数组是从0开始的，一个长度为10的数组，最后一个元素的下标是9 。如果使用左闭右开区间，我们将l=0，r=数组长度，就完成了初始化，如果用闭区间，r=长度-1，不免显得有些多余 。
假设我们确定了使用左闭右开区间，我们再来看前面说的两个问题 。
区间确定了，终止条件也就明确了，左闭右开区间[l, r)不为空的话，r 至少大于等于l + 1 。我们要在区间长度大于1的时候执行二分，所以二分的循环条件应该是while (l + 1 < r) 。
3
那么while里的判断条件呢？
我们列举一下，a[mid] 和v的大小关系无非只有三种 。
推荐阅读
- 消脂瘦腿 4款中药纤腿茶推荐
- 科龙空调哪个好 科龙空调怎么样—科龙空调好不好
- 特产早知道——日照绿茶
- 浅谈，linux防火墙，Firewalld服务
- 负载均衡的5种算法，你了解几种？
- 有机茶栽种及选购知识浅谈
- 茶模,茶行业必备的风景
- 谷歌近期排名不稳定，算法更新正在发生
- 分布式寻址算法
- 实用优先的CSS框架设计引擎，快速实现定制化——Tailwind.css