[LeetCode] Guess Number Higher or Lower

Problem: We are playing the Guess Game. The game is as follows:

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 I picked is higher or lower than your guess.

You call a pre-defined API int guess(int num), which returns 3 possible results:

• -1: The number I picked is lower than your guess (i.e. pick < num).
• 1: The number I picked is higher than your guess (i.e. pick > num).
• 0: The number I picked is equal to your guess (i.e. pick == num).

Return the number that I picked.

Example:

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

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

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

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

Approach: It's a straight forward binary search problem. You can look at the implementation to understand the approach.

Implementation in C#:

        public int GuessNumber(int n)

    {

        int start = 0, end = n;

        while (start <=  end)

        {

            int mid = start + (end - start) / 2;

            int guessRes = guess(mid);

            if (guessRes == 0)

            {

                return mid;

            }

            else if(guessRes == -1)

            {

                end = mid - 1;

            }

            else

            {

                start = mid + 1;

            }

        }

        return -1;

    }

Complexity: O(logn)