leetcode-374. 猜数字大小

JAVA解法

/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is lower than the guess number
 *			      1 if num is higher than the guess number
 *               otherwise return 0
 * int guess(int num);
 */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int left = 1, right = n;
        while (left < right) { // 循环直至区间左右端点相同
            int mid = left + (right - left) / 2; // 防止计算时溢出
            if (guess(mid) <= 0) {
                right = mid; // 答案在区间 [left, mid] 中
            } else {
                left = mid + 1; // 答案在区间 [mid+1, right] 中
            }
        }
        // 此时有 left == right，区间缩为一个点，即为答案
        return left;
    }
}

leetcode原题： 374. 猜数字大小

题解分析

利用二分查找法，定义左右两个边界，只要左边界小于右边界则证明存在还没猜对，进行二分取中点，要用 mid = left + (right - left) / 2 这种是因为使用 mid = （left + right） / 2 可能存在溢出的情况。

判断 guess(mid) <= 0 ？ 是的话证明猜的那个值小于等于 mid， 否则就是大于 mid，循环到最后左边界等于右边界，则成为一个点，则为所要猜的值。