How Binary Search Makes Number Guessing Easy

Problem Statement

You are playing a game where a number is picked from 1 to n, and you have to guess the picked number. For each guess you make, you are given feedback:

• If your guess is higher than the picked number, the API returns -1.

• If your guess is lower than the picked number, the API returns 1.

• If your guess is equal to the picked number, the API returns 0.

Your task is to find the picked number using the fewest guesses possible.

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 <= 2^31 - 1

• The number picked (pick) lies between 1 and n.

Understanding the Problem

The key challenge here is to efficiently determine the number that has been picked within the given range [1, n] while minimizing the number of guesses. Since we get feedback after each guess, this problem lends itself perfectly to binary search. Binary search allows us to halve the search space with each guess, making the solution logarithmic in time complexity.

Key Insights:

1. If the guess is higher than the picked number, we can discard all the numbers greater than the guess.

2. If the guess is lower than the picked number, we can discard all the numbers smaller than the guess.

3. If the guess is correct, we’ve found the number.

Implementation using TypeScript

/** 
 * Forward declaration of guess API.
 * @param {number} num   your guess
 * @return          -1 if num is higher than the picked number
 *                  1 if num is lower than the picked number
 *               otherwise return 0
 * var guess = function(num) {}
 */


function guessNumber(n: number): number {
    let left = 1
    let right = n
    while(left<=right){
        let mid = Math.floor(left + (right - left)/2)
        if(guess(mid)<0){
            right = mid -1
        }
        else if(guess(mid)>0){
            left = mid + 1
        }
        else{
            return mid
        }
    }
    return n
};

How It Works:

The guessNumber function implements a binary search to efficiently find the correct number that has been picked. Here's a step-by-step breakdown of how the code works:

1. Initialize the Search Range:

   • The search starts with the entire range of possible numbers from 1 to n. Two pointers, left and right, are initialized to 1 and n respectively. These pointers represent the current search space.

2. Binary Search Loop:

   • A while loop runs as long as the left pointer is less than or equal to the right pointer. This ensures that the search continues until the correct number is found.

3. Calculate the Midpoint:

   • In each iteration, the midpoint mid of the current search space is calculated using the formula:

       let mid = Math.floor(left + (right - left) / 2);
     

   • This formula helps prevent potential overflow when working with large values of n.

4. Guess API Call:

   • The guess(mid) API is called to check the result of guessing the number at mid.

     • If the result is -1, the guess is too high. This means the correct number is smaller than mid, so the right pointer is moved to mid - 1.

     • If the result is 1, the guess is too low. This means the correct number is larger than mid, so the left pointer is moved to mid + 1.

     • If the result is 0, the guess is correct, and the function returns mid as the picked number.

5. Termination:

   • The loop continues until the correct number is found (when guess(mid) returns 0).

   • In case the loop exits without finding the correct number (which shouldn’t happen), the function returns n.

Time Complexity:

• Time Complexity: O(log n) because we are halving the search space with each guess, using binary search.

• Space Complexity: O(1) since we are only using a few variables (left, right, mid).

Comment if I have committed any mistake. Let's connect on my socials. I am always open for new opportunities , if I am free :P

Linkedin| Twitter | ShowwCase