374

374. Guess Number Higher or Lower (Easy)

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 will tell you whether the number I picked is higher or lower than your guess.

You call a pre-defined API int guess(int num), which returns 3 possible results:

• -1: The number I picked is lower than your guess (i.e. pick < num).
• 1: The number I picked is higher than your guess (i.e. pick > num).
• 0: The number I picked is equal to your guess (i.e. pick == num).

Return the number that I picked.

 

Example 1:

Input: n = 10, pick = 6
Output: 6

Example 2:

Input: n = 1, pick = 1
Output: 1

Example 3:

Input: n = 2, pick = 1
Output: 1

Example 4:

Input: n = 2, pick = 2
Output: 2

 

Constraints:

• 1 <= n <= 231 - 1
• 1 <= pick <= n

Companies:
Google, Apple

Related Topics:
Binary Search, Interactive

Similar Questions:

• First Bad Version (Easy)
• Guess Number Higher or Lower II (Medium)
• Find K Closest Elements (Medium)

Solution 1. Binary Search (L <= R)

// OJ: https://leetcode.com/problems/guess-number-higher-or-lower/
// Author: github.com/lzl124631x
// 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;
    }
};

Solution 2. Binary Search (L < R)

// OJ: https://leetcode.com/problems/guess-number-higher-or-lower/
// Author: github.com/lzl124631x
// 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 == 1) L = M + 1;
            else R = M;
        }
        return L;
    }
};

Or

// OJ: https://leetcode.com/problems/guess-number-higher-or-lower/
// Author: github.com/lzl124631x
// Time: O(logN)
// Space: O(1)
class Solution {
public:
    int guessNumber(int n) {
        int L = 1, R = n;
        while (L < R) {
            int M = R - (R - L) / 2, g = guess(M);
            if (g == -1) R = M - 1;
            else L = M;
        }
        return L;
    }
};