Skip to main content

Guess Number Higher or Lower

Problem 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 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 three possible results:

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

Return the number that I picked.

Examples​

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

Constraints:​

  • 1<=n<=231−11 <= n <= 231 - 1
  • 1<=pick<=n1 <= pick <= n

Algorithm​

  1. Initialization:

    • Set l (low) to 1 and h (high) to n. These variables represent the current search range.
  2. Binary Search Loop:

    • While l is less than or equal to h, continue searching.
    • Compute the middle point mid as (l + h) / 2.
  3. Evaluate guess(mid):

    • Use the guess function to determine how to adjust the search range based on the value returned:
      • If guess(mid) returns 1, it means mid is too low, so adjust l to mid + 1.
      • If guess(mid) returns -1, it means mid is too high, so adjust h to mid - 1.
      • If guess(mid) returns 0, it means mid is the target number, so return mid.
  4. Completion:

    • If the loop exits without finding the number (i.e., l > h), return l. This handles the case where the target number is not exactly in the range but l will be the next potential guess.

Code Implementation​

Python​

def guessNumber(n):
l, h = 1, n

while l <= h:
mid = (l + h) // 2

if guess(mid) == 1:
l = mid + 1
elif guess(mid) == -1:
h = mid - 1
else:
return mid

return l

C++​

class Solution {
public:
int guessNumber(int n) {
long long l = 1;
long long h = n;

while (l <= h) {
int mid = (l + h) / 2;

if (guess(mid) == 1) {
l = mid + 1;
} else if (guess(mid) == -1) {
h = mid - 1;
} else {
return mid;
}
}

return l;
}
};

Java​

public class Solution {
public int guessNumber(int n) {
long l = 1;
long h = n;

while (l <= h) {
int mid = (int)((l + h) / 2);

if (guess(mid) == 1) {
l = mid + 1;
} else if (guess(mid) == -1) {
h = mid - 1;
} else {
return mid;
}
}

return (int)l;
}
}

JavaScript​

function guessNumber(n) {
let l = 1;
let h = n;

while (l <= h) {
let mid = Math.floor((l + h) / 2);

if (guess(mid) === 1) {
l = mid + 1;
} else if (guess(mid) === -1) {
h = mid - 1;
} else {
return mid;
}
}

return l;
}