374.Guess Number Higher or Lower

Tags: [binary_search]

Link: https://leetcode.com/problems/guess-number-higher-or-lower/\#/description

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

I pick a number from1ton. 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 APIguess(int num)which returns 3 possible results (-1,1, or0):

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

Example:

n = 10, I pick 6.
Return 6.

Solution: Binary Search

# 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
        """
        if n < 1:
            raise ValueError('The input is invalid')

        start = 1
        end = n
        while start <= end:
            mid = start + (end - start) / 2
            result = guess(mid)

            if result == 0:
                return mid
            elif result < 0:
                end = mid - 1
            else:
                start = mid + 1

        return None

Note:

• Time complexity = O(lgn), n is the given input.
• We should use mid - 1 to update the end, and use mid + 1 to update the start, not using the start += 1 and end -= 1
• The description of the question says "@return -1 if my number is lower, 1 if my number is higher, otherwise return 0", here the 'my number' means the picked number , it is not the the guessing number we offered to the guess function.