1024. Guess the Ticket
A raffle machine has secretly picked one winning ticket number between 1 and n. You cannot see it, but you can ask the machine about a number x by calling guess(x). It returns 0 when x is the winning ticket, -1 when the winning ticket is smaller than x, and 1 when the winning ticket is larger than x.
Find and return the winning ticket number. You may call guess at most 32 times, so a number-by-number search is not enough. Be careful with integer overflow when n is close to 2^31 - 1.
Example 1
- Input:
- n = 10, game = 6
- Output:
- 6
- Explanation:
The machine's replies steer the search from 5 to 8 to 6, narrowing the range each time until it answers 0 at 6.
Example 2
- Input:
- n = 1, game = 1
- Output:
- 1
- Explanation:
With only one possible ticket, the very first guess of 1 returns 0.
Constraints
1 ≤ n ≤ 231 - 1
1 ≤ winning ticket ≤ n
At most 32 calls to guess
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Calls
- You may call
guess(num)at most 32 times per case. It is provided; you do not write it.
Expected complexity
- Time
- O(log n)
- Space
- O(1)