Guess Number Higher or Lower

Условие

Задана игра, в которой загаданное число находится между 1 и n. Ваша задача — угадать это число. Вы вызываете функцию guess(int num), которая возвращает:

• -1, если загаданное число меньше num.

• 1, если загаданное число больше num.

• 0, если num — загаданное число.

Напишите функцию guessNumber(int n), которая возвращает загаданное число.

Примеры

Input: n = 10, pick = 6

Output: 6

Input: n = 1, pick = 1

Output: 1

Input: n = 2, pick = 1

Output: 1

Решение

fun guessNumber(n: Int): Int {
    var left = 1
    var right = n

    // Используем бинарный поиск для оптимального поиска числа
    while (left <= right) {
        val mid = left + (right - left) / 2
        val result = guess(mid)  // Вызываем функцию guess

        when (result) {
            0 -> return mid  // Число угадано
            -1 -> right = mid - 1  // Загаданное число меньше mid
            1 -> left = mid + 1  // Загаданное число больше mid
        }
    }

    return -1  // Это значение никогда не будет достигнуто при корректных входных данных
}

Временная сложность

O(log n), так как используется бинарный поиск.

Пространственная сложность

O(1), так как не используется дополнительная память, зависящая от размера входных данных.