猜数字大小

题目形容：猜数字游戏的规定如下：

  • 每轮游戏，我都会从 1 到 n 随机抉择一个数字。 请你猜选出的是哪个数字。
  • 如果你猜错了，我会通知你，你猜想的数字比我选出的数字是大了还是小了。

你能够通过调用一个事后定义好的接口 int guess(int num) 来获取猜想后果，返回值一共有 3 种可能的状况（-1，1 或 0）：

  • -1：我选出的数字比你猜的数字小 pick < num
  • 1：我选出的数字比你猜的数字大 pick > num
  • 0：我选出的数字和你猜的数字一样。祝贺！你猜对了！pick == num

返回我选出的数字。

示例阐明请见LeetCode官网。

起源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

解法一：二分查找法

典型的二分查找问题，首先low初始值为1，high初始值为num，二分查找过程如下：

  • 循环的前提是low不大于high；
  • 而后mid的值为low + (high - low) / 2，而后调用guess(num)办法进行判断；
  • 如果返回-1，则high的值置为mid - 1，而后进行下一轮解决；
  • 如果返回1，则low的值置为mid + 1，而后进行下一轮解决；
  • 如果返回0，则返回mid值，该值即为选出的数字。
public class LeetCode_374 extends GuessGame {    /**     * 二分查找     *     * @param num     * @return     */    public static int guessNumber(int num) {        int low = 1, high = num;        while (low <= high) {            int mid = low + (high - low) / 2;            if (guess(mid) == -1) {                high = mid - 1;            } else if (guess(mid) == 0) {                return mid;            } else if (guess(mid) == 1) {                low = mid + 1;            }        }        return -1;    }    public static void main(String[] args) {        System.out.println(guessNumber(2126753390));    }}class GuessGame {    /**     * 假如1702766719是最终的后果     * 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     */    public static int guess(int num) {        if (num > 1702766719) {            return -1;        } else if (num == 1702766719) {            return 0;        } else {            return 1;        }    }}
【每日寄语】 总之岁月漫长，然而值得期待。