「力扣」第 374 题：猜数字大小

发布日期: 2017-05-25

说明：文本首发在力扣的题解版块，更新也会在第 1 时间在上面的网站中更新，这篇文章只是上面的文章的一个快照，您可以点击上面的链接看到其他网友对本文的评论。

我们正在玩一个猜数字游戏。游戏规则如下：
我从 1 到 n 选择一个数字。你需要猜我选择了哪个数字。
每次你猜错了，我会告诉你这个数字是大了还是小了。
你调用一个预先定义好的接口 guess(int num)，它会返回 3 个可能的结果（-1，1 或 0）：

-1 : 我的数字比较小
1 : 我的数字比较大
0 : 恭喜！你猜对了！
示例 :

输入: n = 10, pick = 6
输出: 6

借本题说一说取中位数的写法（Python 代码、Java 代码）

以下代码是根据我在刷题过程中总结出来的最好用的二分法模板写成。我专门把这个二分法模板好用的地方、使用它的技巧和注意事项整理在了「力扣」第 35 题：搜索插入位置的题解《特别好用的二分查找法模板（Python 代码、Java 代码）》，希望能对大家有所帮助。

参考代码：

注意：以下虽然我用两种语言作答，但是它们的逻辑上还有一点点区别，那就是在取中位数的时候，答案在上面那篇题解中。

def guess(num):
    pass


class Solution(object):
    def guessNumber(self, n):
        left = 1
        right = n
        while left < right:
            # mid = left + (right - left) // 2
            mid = (left + right) >> 1
            if guess(mid) == 1:
                left = mid + 1
            else:
                right = mid
        # 最后剩下的数一定是所求，无需后处理
        return left

class GuessGame {

    private static final int NUM = 6;

    int guess(int num) {
        if (num == NUM) {
            return 0;
        } else if (num < NUM) {
            return -1;
        }
        return 1;
    }
}


public class Solution extends GuessGame {

    public int guessNumber(int n) {
        int left = 1;
        int right = n;
        while (left < right) {
            // int mid = left + (right - left + 1) / 2;
            int mid = (left + right + 1) >>> 1;
            int guessNum = guess(mid);
            if (guessNum == -1) {
                right = mid - 1;
            } else {
                left = mid;
            }
        }
        // 最后剩下的数一定是所求，无需后处理
        return left;
    }


    public static void main(String[] args) {
        Solution solution = new Solution();
        int n = 10;
        int guessNumber = solution.guessNumber(n);
        System.out.println(guessNumber);
    }
}

以上是本题题解，以下才是本文真正想说的，你应该已经注意到了，上面的示例代码中，mid = left + (right - left) // 2 和 int mid = left + (right - left + 1) / 2; 都被我注释掉了，不是因为它们不正确，而是因为它们不够好，下面就来具体说说。

1、最早学习二分法的时候，写中位数的索引是这样的：

Python 代码：

mid = (left + right) // 2

Java 代码：

int mid = (left + right) / 2;

2、后来被告知在 left 和 right 很大的时候，left + right 会发生整型溢出，变成负数，这是一个 bug 得改！

于是我们写成：

Python 代码：

mid = left + (right - left) // 2

Java 代码：

int mid = left + (right - left) / 2;

然后又被告知 mid = left + (right - left) // 2 在 right 很大、 left 是负数且很小的时候， right - left 也有可能超过 int 类型能表示的最大值，只不过一般情况下 left 和 right 表示的是数组索引值，left 是非负数，因此 right - left 溢出的可能性很小。

3、最后，在 Java 的 JDK 的 Collections 和 Arrays 提供的 binarySearch 方法里看到了，中位数是这样取的：

int mid = (low + high) >>> 1;

怎么又变成“+”了，一头雾水啊，会整型溢出吗？后来查了查资料，有可能会整型溢出的，不过结果依然正确。下面是原因：

left + right 在发生整型溢出以后，会变成负数，此时如果除以 2 ，mid 是一个负数，但是经过无符号右移，可以得到在不溢出的情况下正确的结果。

首先解释“无符号右移”，在 Java 中，无符号右移运算符 >>> 和右移运算符 >> 有区别：

右移运算符 >> 在右移时，丢弃右边指定位数，左边补上符号位；
无符号右移运算符 >>> 在右移时，丢弃右边指定位数，左边补上 $0$，也就是说，对于正数来说，二者一样，而负数通过 >>> 后能变成正数。

了解了这一点，就能够理解 Java 中用 int mid = (low + high) >>> 1; 的原因了，关键不在 “+” ，而是“无符号右移”，在 Java 的 Collections 和 Arrays 提供的 binarySearch 方法里，low 和 high 都表示索引值，它们都是非负数，即使相加以后整型溢出，结果还是正确的，“位运算”本身就比其它运算符快，因此使用“+”和“无符号右移”是既快又好的做法。

如果你用 Java 写的话，不妨做下面的试验：

用“+”和除法，不能通过，提示也很清楚了。