[Leetcode]374. Guess Number Higher or Lower

https://leetcode.com/problems/guess-number-higher-or-lower/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.

看着就是二分搜索，但是每太看懂他的意思，他的guess function用来干啥的呢。

先二分搜索试试看。这个二分跟普通的二分就一点不一样，不是让你二分search 而是二分看是什么数，换汤不换药，以前是已知数让你看在不在，现在是他告诉你大小，你自己缩小范围，信息点给的是一样的，guess（int num）这个函数来指示大了还是小了，我们好挪动范围。这道题最神奇的地方在于，题目对-1， 和1这个返回值 的理解。我一开始就理解反了，真么着都不对，心塞塞，后来调过来就好了，呵呵。还有一个不能饶恕的错误，第一次提交竟然因为没检查low 比 high小 而Stack Overflow 了！不能再犯！

但是感觉狗家给这个题不是很正常，边界条件要问好，估计这才是重点。

AC Solution, Recursion:

public class Solution extends GuessGame {

    int result = 0;
    public int guessNumber(int n) {    
        return helper(1, n);
    }
    public int helper(int low, int high){
        if(low >= high){
            return low;
        }
        int mid = low + (high - low) / 2;
        if(guess(mid) == 0){
            return mid;
        }
        else if(guess(mid) == 1){
            return helper(mid+1, high);
        }
        else{
            return helper(low, mid-1);
        }
    }
}

AC Solution, Iteration:

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int low = 1;
        int high = n;
        while(low <= high){
            int mid = low + (high - low)/2;
            if(guess(mid) == 0){
                return mid;
            }
            if(guess(mid) == 1){
                low = mid + 1;
            }
            else
            {
                high = mid -1;
            }
        }
        return -1;
    }
}