leetCode-374:Guess Number Higher or Lower

问题描述

给定一个正整数 n，要求在 1~n 范围内找到预设的数字。猜测数字规则如下：每次调用 int guess(int num) 获取猜测的值与预设的值比较结果，如果相同则返回 0，如果猜测的值比预设的值大，则返回 -1，如果猜测的值比预设的值小，则返回 1。题目链接：点我

样例输入输出

输入：n = 10, pick = 6

输出：6

输入：n = 1, pick = 1

输出：1

问题解法

用二分查找进行求解，代码如下

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

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int start = 1;
        int end = n;
        while (start <= end) {
            int middle = start + (end - start) / 2;
            int temp = guess(middle);
            if (temp == 0) {
                return middle;
            }

            if (temp > 0) {
                start = middle + 1;
            } else {
                end = middle - 1;
            }
        }
        
        return n;
    }
}