374. Guess Number Higher or Lower

Задача

Мы играем в игру “Угадай число”. Игра заключается в следующем:

Я загадываю число от 1 до n . Ты должен угадать, какое число я загадал (загаданное число остается неизменным на протяжении всей игры).

Каждый раз, когда ты ошибаешься, я буду говорить тебе, больше или меньше загаданное число по сравнению с твоим предположением.

Ты вызываешь предопределенный API int guess(int num) , который возвращает три возможных результата:

• -1: Твое предположение больше, чем число, которое я загадал (т.е. num > pick).
• 1: Твое предположение меньше, чем число, которое я загадал (т.е. num < pick).
• 0: Твое предположение равно числу, которое я загадал (т.е. num == pick).

Верни число, которое я загадал.

Примеры

Пример 1

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

Пример 2

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

Пример 3

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

Решение

Решение

/**
 * Временная сложность: O(log N)
 * Пространственная сложность: O(1)
 */
var guessNumber = function(n) {
    let left = 1;
    let right = n;
 
    while (left <= right) {
        const myGuess = left + Math.floor((right - left) / 2);
        const delta = guess(myGuess);
 
        if (delta === 1) {
            left = myGuess + 1;
        } else if (delta === -1) {
            right = myGuess - 1;
        } else {
            return myGuess;
        }
    }
};