GuessNumberHigherOrLower [source code]

public class GuessNumberHigherOrLower {
static
/******************************************************************************/
/* 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 (n == 1) return 1;
        int lo = 1, hi = n;
        while (lo <= hi) {
            int mid = lo + (hi - lo) >> 1;
            if (guess(mid) == 0) return mid;
            else if (guess(mid) < 0) hi = mid - 1;
            else lo = mid + 1;
        }
        return -1;
    }
}
/******************************************************************************/
    static public class GuessGame {
        public int guess(int guess) {
            return 1;
        }
    }

    public static void main(String[] args) {
        GuessNumberHigherOrLower.Solution tester = new GuessNumberHigherOrLower.Solution();
    }
}

总体思路还是很简单的, 就是API 有点唬人, 最后的速度是1(17).
这题的一个难点是怎么把 GuessGame 这个 super class 写到我这个 JAVA 模板里面. 只有当 subclass 的 object 被 call 了 guessNumber, 我们才知道 n, 那么 superclass 怎么样才能提前知道这个 n 呢? 因为很明显, MyNumber 这个值, 肯定是要存在 superclass 里面的, 这样才可以persist throught multiples calls of guess.

注意这里算 mid 的时候用 shift 来代替除法. 不过最后的速度好像并没有多大变化;

另外, 这个是 discussion 里面关于算 mid 的时候的 overflow 问题的一个现身说法:
very strange...

for the testcase:

2126753390
1702766719

if I use the line "int mid = i + (j - i) / 2", then it can pass

if I replace it with "int mid = (j + i) / 2", which mathematically are the same it will return Time Limit Exceeded error. And this line works fine if the input number is not that big...

这个是 editorial 里面的另外一个思路:

public class Solution extends GuessGame {  
    public int guessNumber(int n) {  
        int low = 1;  
        int high = n;  
        while (low <= high) {  
            int mid1 = low + (high - low) / 3;  
            int mid2 = high - (high - low) / 3;  
            int res1 = guess(mid1);  
            int res2 = guess(mid2);  
            if (res1 == 0)  
                return mid1;  
            if (res2 == 0)  
                return mid2;  
            else if (res1 < 0)  
                high = mid1 - 1;  
            else if (res2 > 0)  
                low = mid2 + 1;  
            else {  
                low = mid1 + 1;  
                high = mid2 - 1;  
            }  
        }  
        return -1;  
    }  
}

这个叫做Ternary Search, 其实跟 Binary Search 是差不多的, 无非是这个ternary 就是分三段了; 最后的速度其实也就跟 Binary Search 差一个constant factor, 看看就好;

Problem Description

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.
Difficulty:Easy
Category:Algorithms
Acceptance:34.96%
Contributor: LeetCode
Companies
google
Related Topics
binary search
Similar Questions
First Bad Version Guess Number Higher or Lower II