从老鼠试毒问题来看二分法

很多人对于二分法的理解比较片面，之前碰到一个题目 " 从一个先升序后降序的数列中，比如 1 2 3 7 4 3 2 中运用二分法去查找一个给定的元素"，很多人说根本不能二分，因为没有排序。其实 这道题完全可以使用二分查找进行解答， 如果你觉得不可以的话，很可能对二分法理解还比较片面。 这里以另外一个更加有趣（至少我认为）的例子来讲解一下二分法。

题目

面试题：有1000个一模一样的瓶子，其中有1瓶是毒药，老鼠喝了有毒的会在24h之后死亡。求最少需要多少老鼠才能在24h里找到有毒的那瓶。

解法

这道题的解法有很多，今天我们来聊下用二分法来解这道题。这道题似乎和我们看的常见的二分法有很大的区别，但是仔细想一下， 二分法本质是将问题的规模缩小到原有的一半。类似的，三分法就是将问题规模缩小为原来的1/3,带着这样的思想我们再来看一下。

我们先对1000个瓶子进行编号，从1-1000这样子。不过我们不是通过我们大家平时生活中使用的十进制，而是使用在计算机中使用的二进制， 同时让大家感受一下二进制的魅力。

为了方便讲解，我们假设不是1000个瓶子，而是4个。

我们来编一下号：

00 // #1
01 // #2
10 // #3
11 // #4

我们的目标是找到哪个瓶子有毒，换句话说我们目标是找到有毒瓶子的编号，再换句话说我们的目标是 找到有毒瓶子的2个bit分别是什么，是0还是1.

比如有毒的是3号瓶子，那么我们就是想确认第一个bit是0，第二个bit是1，即11，转化为10进制就是3号。

那么如何确定每一个bit是什么呢？ 回想一下，我们手上有老鼠，老鼠有两个state，alive 或者 died，这就是我们拥有的全部。

接下来我们逐一对瓶子进行分组，分组的依据就是每一个bit的值。

比如:

// 00 01     #g1:1  第一个bit是0
// 10 11     #g1:2  第一个bit是1
// 00 10     #g2:1  第二个bit是0
// 01 11     #g2:2  第二个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。

我会在之后的文章中进行讲解小球的问题最优策略， 并解释为什么这是最优策略。

思考题

基于比较的排序都无法逃脱nlogn时间复杂度的命运，这是为什么？能否利用本篇文章的思想进行解释？