1.11 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.

Method

Binary Search

Time and Space Complexity

O(logN)

Code

public class Solution extends GuessGame {

   public int guessNumber(int n) {
       if (n < 1){
           return n;
       }
       int left = 1;
       int right = n;

       while (left + 1 < right){
             int mid = (right - left) / 2 + left;

             int f = guess(mid);

             if (f == 0){
                 return mid;
             } else if (f > 0){
                 left = mid;
             } else {
                 right = mid;
             }
       }
       if (guess(left) == 0){
           return left;
       }
       return right;

}

}