1mS Java solution using binary search


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

  • 0
    D

    I don't know why I change the guess number in my loop using this
    g = (low + high) / 2
    equation doesn't work, it always give me Time Exceeded Error. I think this equation should be equal to g = low + (high - low) / 2


  • 0
    T

    I have the same question, but the result is java.lang.stackOverFlowError, when I used the recursive algorithm.
    Why it can't accepted when (low+high)/2? What is the difference between them?


  • 0
    3

    @dadinghh2 low + high could exceed max value of integer.

    use long low and long high, then g = (int) ((low + high) / 2) works


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.