Задача: Игра в угадайку

Условие: играем в угадайку по следующей схеме:

Выбирается число от 1 до n. Надо отгадать загаданное число. После каждой неудачной попытки говорится больше или меньше заданное число.

Надо реализовать API:

-1: загаданное число больше выбранного;

1: загаданное число меньше выбранного;

0: загаданное число и выбранное совпали.

Необходимо вернуть загаданное число. 

Пример:

Ввод: n = 10, pick = 6

Вывод: 6

Решение: Python

Сложности:

Временная сложность: O(logn)
Пространственная сложность: O(1)

Код:

# The guess API is already defined for you.
# @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
# def guess(num: int) -> int:

class Solution:
    def guessNumber(self, n: int) -> int:
        l=0
        r=n
        while l<=r:
            m=(l+r)>>1
            if guess(m)==0:
                return m
            elif guess(m)==-1:
                r=m-1
            else:
                l=m+1