CA 16 - Guess The Number Higher or Lower

#algorithms #beginners #coding #computerscience

Problem Statement

We are playing the Guess Game.

I pick a number from 1 to n. You have to guess which number I picked.
Every time you guess wrong, I will tell you whether the number is higher or lower than your guess.

You call a pre-defined API:

guess(num) returns:

-1 → your guess is higher than the picked number
1 → your guess is lower than the picked number
0 → your guess is correct

Return the number that I picked.

Examples:

Input: n = 10, pick = 6
Output: 6

Input: n = 1, pick = 1
Output: 1

Input: n = 2, pick = 1
Output: 1

My Goal

For this problem, my goal was to:

Minimize the number of guesses
Understand efficient searching techniques
Avoid brute-force checking
Apply a well-known algorithm (Binary Search)

Solution

I used Binary Search to efficiently find the picked number.

Idea:

Start with range from 1 to n
Find middle value
Call guess(mid)
If result is 0 → found the number
If -1 → search left half
If 1 → search right half

This reduces the search space by half each time.

Solution Code (Python)

def guessNumber(n):
    l = 1
    h = n

    while l <= h:
        m = (l + h) // 2

        g = guess(m)

        if g == 0:
            return m
        elif g == -1:
            h = m - 1
        else:
            l = m + 1