Question
Formatted question description: https://leetcode.ca/all/374.html
374 Guess Number Higher or Lower
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 predefined 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 :
Input: n = 10, pick = 6
Output: 6
Algorithm
Binary search.
Code
Java

public class Guess_Number_Higher_or_Lower { 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; int res = guess(mid); if (res == 0) return mid; else if (res < 0) high = mid  1; else low = mid + 1; } return 1; } } } // stub class GuessGame { public int guess(int i) { return 0; } }

// OJ: https://leetcode.com/problems/guessnumberhigherorlower/ // Time: O(logN) // Space: O(1) class Solution { public: int guessNumber(int n) { int L = 1, R = n; while (L <= R) { int M = L + (R  L) / 2, g = guess(M); if (g == 0) return M; if (g == 1) L = M + 1; else R = M  1; } return 1; } };

# The guess API is already defined for you. # @param num, your guess # @return 1 if my number is lower, 1 if my number is higher, otherwise return 0 # def guess(num): class Solution(object): def guessNumber(self, n): """ :type n: int :rtype: int """ l, r = 1, n while l < r: m = l + (r  l) / 2 g = guess(m) if g == 1: r = m  1 elif g == 1: l = m + 1 else: return m return l