Guess Number Higher or Lower

Question

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'll tell you whether the number is higher or lower.

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

-1 : My number is lower
 1 : My number is higher
 0 : Congrats! You got it!

Example:

n = 10, I pick 6.

Return 6.

Tags

• Binary Search

Thought

The method is simple, we just use binary search should be fine.

The only problem is to make sure don't ignore any items when using binary search because the average of an even number and an odd number is not actually the middle number.

Code

# The guess API is already defined for you.
# @param num, your guess
# @return -1 if my number is lower, 1 if my number is higher, otherwise return 0
# def guess(num):

class Solution(object):
    def guessNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        # binary search method
        low = 0
        high = n

        def guessHighLow(low, high):
            if (high + low) % 2 == 1:
                mid = (high + low ) / 2 + 1
            else:
                mid = (high + low ) / 2
            if guess(mid) == 1:
                return guessHighLow(mid, high)
            elif guess(mid) == -1:
                return guessHighLow(low, mid)
            else:
                return mid

        return guessHighLow(low, high)