/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is higher than the picked number
 *			      1 if num is lower than the picked number
 *               otherwise return 0
 * int guess(int num);
 */

 public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int lower = 1;
        int higher = n;
        while (lower <= higher) {
            // This simplified expression will cause time limit exceeded.
            // So either use long, or rewrite in a form that doesn't risk overflow.
            // int mid = (higher + lower) / 2;
            int mid = lower + (higher - lower) / 2;
            int result = guess(mid);
            if (result == 0) {
                return mid;
            }
            else if (result > 0) {
                lower = mid + 1;
            }
            else if (result < 0) {
                higher = mid - 1;
            }
        }
        return 0;
    }
}

/** 
 * Forward declaration of guess API.
 * @param  num   your guess
 * @return 	     -1 if num is higher than the picked number
 *			      1 if num is lower than the picked number
 *               otherwise return 0
 * unsafe fn guess(num: i32) -> i32 {}
 */

 impl Solution {
  unsafe fn guessNumber(n: i32) -> i32 {
      let mut lower = 1;
      let mut higher = n;

      while lower <= higher {
          let mut mid = lower + (higher - lower) / 2;
          let result = guess(mid);

          if result == 0 {
              return mid;
          }
          else if result > 0 {
              lower = mid + 1;
          }
          else { // result < 0
              higher = mid - 1;
          }
      }

      return 0;
  }
}