Description
We are playing the Guess Game. I pick a number from 1 to n. You guess, and I tell you if it is higher or lower. Use binary search to find my number efficiently.
Examples
Input:
n = 10, pick = 6Output:
6Explanation:
Binary search finds 6.
Input:
n = 100, pick = 42Output:
42Explanation:
Using binary search on range [1,100]: start with mid=50 (too high), then mid=25 (too low), then mid=37 (too low), then mid=43 (too high), then mid=40 (too low), then mid=41 (too low), finally mid=42 (correct). Binary search efficiently narrows down to find 42.
Input:
n = 7, pick = 7Output:
7Explanation:
Binary search on range [1,7]: start with mid=4 (too low), then mid=6 (too low), finally mid=7 (correct). This demonstrates the edge case where the picked number is at the upper boundary of the range.
Constraints
- •
1 ≤ n ≤ 2³¹ - 1