Guess Number Higher or Lower
The key idea
The answer space
1..n is sorted, so each guess call is a comparison that tells you which half to discard. Halving the range every call finds the pick in O(log n).Problem
We are playing the Guess Game. I pick a number from 1 to n, and you must guess which one I picked. Every time you guess wrong, I tell you whether the number I picked is higher or lower than your guess. You call a predefined API guess(num), which returns three possible results: -1 means your guess num is higher than the number I picked, 1 means your guess num is lower than the number I picked, and 0 means your guess num is equal to the number I picked. Return the number that I picked.
Constraints
1 <= n <= 2^31 - 11 <= pick <= n
Examples
Input: n = 10, pick = 6
Output: 6
Input: n = 1, pick = 1
Output: 1
Input: n = 2, pick = 1
Output: 1
Complexity
Time: O(log n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Binary Search problems
- Binary SearchEASY
- Capacity To Ship Packages Within D DaysMEDIUM
- Find First and Last Position of Element in Sorted ArrayMEDIUM
- Find in Mountain ArrayHARD
- Find K Closest ElementsMEDIUM
- Find Minimum in Rotated Sorted ArrayMEDIUM
- Find Peak ElementMEDIUM
- First Bad VersionEASY
- Koko Eating BananasMEDIUM
- Lowest Common Ancestor of a Binary Search TreeMEDIUM
- Median of Two Sorted ArraysHARD
- Search a 2D MatrixMEDIUM