很多人对于二分法的理解比较片面，之前碰到一个题目，从一个先升序后降序的数列中，比如 1 2 3 7 4 3 2 中运用二分法去查找一个给定的元素，很多人说根本不能二分，因为没有排序。其实 这道题完全可以使用二分查找进行解答， 如果你觉得不可以的话，很可能对二分法理解还比较片面。 这里以另外一个更加有趣（至少我认为）的例子来讲解一下二分法。
题目
面试题： 有 1000 个一模一样的瓶子，其中有 1 瓶是毒药，老鼠喝了有毒的会在 24h 之后死亡。求最少需要多少老鼠才能在 24h 里找到有毒的那瓶。
解法
这道题的解法有很多，今天我们来聊下用二分法来解这道题。 这道题似乎和我们看的的常见的二分法有很大的区别，但是仔细想一下， 二分法本质是将问题的规模缩小到原有的一半，带着这样的思想我们再来看一下。类似的，三分法就是将问题规模缩小为原来的 1/3.
我们先对 1000 个瓶子进行编号，从 1-1000 这样子。 不过我们不是通过我们大家平时生活中使用的十进制，而是使用再计算机中使用的二进制， 同时让大家感受一下二进制的魅力。
为了方便讲解，我们假设不是 1000 个瓶子，而是 4 个。
我们来编一下号：
1 | 00 // #1 |
我们的目标是找到哪个瓶子有毒，换句话说我们目标是找到有毒瓶子的编号，再换句话说我们的目标是
找到有毒瓶子的 3 个 bit 分别是什么，是 0 还是 1.
比如有毒的是 3 号瓶子，那么我们就是想确认第一个 bit 是 0，第二个 bit 是 1，第三个 bit 是 1，即 011，转化为 10 进制就是 3 号。
那么如何确定每一个 bit 是什么呢？ 回想一下，我们手上有老鼠，老鼠有两个 state，alive 或者 died，这就是我们拥有的全部。
接下来我们逐一对瓶子进行分组，分组的依据就是每一个 bit 的值。
比如:
1 |
|
我们来找第一个老鼠#1 来喝 g:1:1, 如果他死了，那么毒就在这一组，也就是说毒的第一个 bit 是 0，否则是 1
我们来找第二个老鼠#2 来喝 g:2:1, 如果他死了，那么毒就在这一组，也就是说毒的第二个 bit 是 0，否则是 1
所以我们可以看出, 两只老鼠就搞定了，我们按照这个思路，可以推到出 1000 个瓶子只需要 10 个瓶子, 即 log2 1000， 2 的 10 次方是 1024，因此 10 个老鼠够了，如果 1025 个瓶子的话，就需要 11 个老鼠了。
如果你仔细思考的话，不难看出，我们是在用老鼠喝了水之后的反应（生或死）来进行判断每一个 bit 的数字，不管生死，我们总能得出这个 bit 的值，是 0 还是 1. 因此每使用一只老鼠我们都将问题规模缩小为原来的 1／2. 这是典型的二分法。
这是最优解么
是的，这是最优解，如果你愿意用严格的数学来证明的话，你可以试一下数学归纳法。 如果你想感性的判断一下的话，可以继续往下读。
什么是最优解？ 最优解就是要让未知世界无机可乘，也就是说在最坏的情况下得到最优（现实世界都是未知的）。上面的例子，不管小老鼠是生还是死，我们都可以将问题规模缩小到 1/2. 也就是说最坏的情况就是最好的情况，也就是说没有最坏情况。
那么我们是否可以将问题规模缩小的 1／3 或者更小呢？
我们可以三分么
简单来说，不可以， 因为老鼠只有两种 observable state， 即 alive， died. 假如我们有 10 个小球，其中有一个是异常的，其他 9 个都是一样的，我们怎么才能通过最少的称量来确定是哪一个异常，是重还是轻？ 这个时候我们就可以使用三分法了，为什么？因为天平有三个 state， 平衡，左倾，右倾，使得我们”有可能“ 将问题规模缩小为 1/3， 事实上，确实可以实现将问题规模缩小到 1/3。
我会在之后的文章中进行讲解小球的问题最优策略， 并解释为什么这是最优策略。
Bonus
基于比较的排序都无法逃脱 nlogn 时间复杂度的命运，这是为什么？能否利用本篇文章的思想进行解释？
