Binary Search to Guess Number Game (C++ Coding Exercise)


Given a API guess(int num) which will return three possible results (0 – you guess right, -1 my answer lower, and 1 my answer higher), your task is to find the the number between 1 to n – implement the guessNumber(int n) function.

Since the number from 1 to n is sorted – continious, we can use binary search O(logN) to find the answer.

Each iteration in binary search, we invoke the guess API and narrow down the search range to half (drop another half) if the middle number is not the answer.

We can implement the binary search using recursion:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// Forward declaration of guess API.
// @param num, your guess
// @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num);
 
class Solution {
public:
    int guessNumber(int n) {
        return guessNumber(1, n);   
    }
    
private:
    int guessNumber(int low, int high) {
        int mid = low + (high - low) / 2;
        int x = guess(mid);
        if (x == 0) return mid;
        if (x == -1) return guessNumber(low, mid - 1);
        return guessNumber(mid + 1, high);
    }
};
// Forward declaration of guess API.
// @param num, your guess
// @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num);

class Solution {
public:
    int guessNumber(int n) {
        return guessNumber(1, n);   
    }
    
private:
    int guessNumber(int low, int high) {
        int mid = low + (high - low) / 2;
        int x = guess(mid);
        if (x == 0) return mid;
        if (x == -1) return guessNumber(low, mid - 1);
        return guessNumber(mid + 1, high);
    }
};

It is also very simple to implement the binary search algorithm using the iterative manner as long as we halve the search range after comparing the middle number with the target number.

THe recursive binary search implementation is easier to write, and the compiler will generate the call stacks – if the average search depth e.g. logN is large – stack may overflow.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// Forward declaration of guess API.
// @param num, your guess
// @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num);
 
class Solution {
public:
    int guessNumber(int n) {
        int low = 1;
        int high = n;
        while (low <= high) {
            int mid = low + (high - low) / 2; // avoid integer overflow
            switch(guess(mid)) {
                case 0: return mid;
                case -1: high = mid - 1; break;
                case 1: low = mid + 1; break;
            }
        }
        return -1; // indicate the number is not in the range. (NOT FOUND)
    }
};
// Forward declaration of guess API.
// @param num, your guess
// @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
int guess(int num);

class Solution {
public:
    int guessNumber(int n) {
        int low = 1;
        int high = n;
        while (low <= high) {
            int mid = low + (high - low) / 2; // avoid integer overflow
            switch(guess(mid)) {
                case 0: return mid;
                case -1: high = mid - 1; break;
                case 1: low = mid + 1; break;
            }
        }
        return -1; // indicate the number is not in the range. (NOT FOUND)
    }
};

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
386 words
Last Post: Simple xargs Batch Implementation for Windows
Next Post: The Array Unique Function in Javascript - Remove Duplicates in Javascript Array

The Permanent URL is: Binary Search to Guess Number Game (C++ Coding Exercise)

Leave a Reply