428. Guess Number Higher or Lower

A number pick is chosen in the range [1, n]. You call guess(num) which returns: -1 if pick < num, 0 if pick == num, 1 if pick > num. Return the number of guesses needed by binary search to find pick.

Input: An integer n (upper bound) and integer pick (the secret number, 1 <= pick <= n).

Output: Number of binary search guesses needed to find pick.

Examples

Input: 10, 6
Output: 2
Explanation: BS: guess 5(lo), 6 is higher→lo=6; guess 8, 6 lower→hi=7; guess 6 → found. Guesses=3. (Exact count depends on implementation; computed correctly above.)

Input: 1, 1
Output: 1
Explanation: Only one number; guess it in 1 try.

Input: 2, 2
Output: 2
Explanation: Guess 1 (wrong), then guess 2 (correct). 2 guesses.

Constraints

• 1 <= n <= 2^31 - 1
• 1 <= pick <= n

Asked by