LeetCode 374. Guess Number Higher or Lower

題目

We are playing the Guess Game. The game is as follows:

I pick a number from 1 to n. You have to guess which number I picked.

Every time you guess wrong, I'll tell you whether the number is higher or lower.

You call a pre-defined API guess(int num) which returns 3 possible results (-1, 1, or 0):

-1 : My number is lower   
 1 : My number is higher  
 0 : Congrats! You got it!

Example:
n = 10, I pick 6.  
Return 6.

翻譯

給一個n值，猜一個1~n之間神秘數字x，根據猜測的結果回傳值，如果回傳-1代表神秘數字比你猜的還低，回傳1代表比你猜的還高，回傳0代表你猜對了。最後你要回傳x到底是多少。

範例：

• n = 1000，神秘數字是987 ，猜500，得到-1
• 猜 1000，得到 1
• 猜 987，得到 0， 因此最後要回傳答案 987

思路

1. 最小值為min，最大值為max，猜測值 g = (min+max)/2
2. 一開始min = 1， max = n ， g = (1+n) /2
3. 如果得到1， min = g
4. 如果得到-1， max = g
5. 重複以上步驟值到猜到為止，因為這提沒提供javascript，只好用java來解

解題

/* The guess API is defined in the parent class GuessGame.
   @param num, your guess
   @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
      int guess(int num); */

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        if(guess(n) == 0){
            return n;
        }

        int min = 1; // 最小為1
        int max = n; // 最大為n
        int g = min+(max-min)/2; //先猜(min+max)/2
        int result = guess(g);

        while(max > min){

            // 猜的值太小，min=g
            if(result == 1){
                min = g;
            }

            // 猜的值太大，max=g
            if(result == -1){
                max = g;
            }

            // equal with  (min+max)/2，but use  min+(max-min)/2 could avoid max+min > Integer.max
            g = min+(max-min)/2; 

            result = guess(g);
        }

        return g;

    }
}