Efficiently Finding Picked Number using Binary Search Algorithm

Efficiently Finding Picked Number using Binary Search Algorithm

Approach

The guess number method takes an integer input nand returns an integer which is the number that was picked by a function called guess().

The guess() the function is a forward declaration of an API that is provided. The API takes an integer input 'num' and returns one of the following:

-1 if the input num is higher than the picked number
1 if the input num is lower than the picked number
0 if the input num is equal to the picked number

The guess number method uses a binary search algorithm to find the picked number. The algorithm starts by defining two variables, start and end, which represents the range in which the picked number is being searched. start is initialized to 1 and end is initialized to the value of n.

The method then enters a while loop that continues until start is greater than end. Within the loop, a variable called mid is defined as the average of start and end. The method then calls the guess() function with the value of mid as the input.

The guess() the function returns a value indicating whether mid is higher or lower than the picked number.

If the guess() function returns 0, then the method returns the value of mid as the picked number. If the guess() function returns -1, the method updates the value of end to be mid-1 and if it returns 1, the method updates the value of start to be mid+1 and continues the loop until the picked number is found.
If the loop ends and the picked number isn't found, the method returns -1.

Code:

/** 
 * Forward declaration of guess API.
 * @param  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
 * int guess(int num);
 */

class Solution extends GuessGame {
    public int guessNumber(int n) {

        int start = 1; // initialize the start of the search range
        int end = n; // initialize the end of the search range

        while ( start <= end){
            int mid = start + (end - start)/2; // find the middle of the search range

            if(guess(mid) == 0){
                return mid; // the middle is the picked number
            }

            else if(guess(mid) == -1){
                end = mid - 1; // the picked number is lower than mid
            } 

            else if(guess(mid) == 1){
                start = mid + 1; // the picked number is higher than mid
            }


        }
       return -1; // the picked number was not found
    }
}