Угадай число

Легкая

easy , binary search

23 February 2024

Описание задачи #

Мы играем в игру, где вы должны угадать загаданное число.

Игра заключается в следующем.

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

Вы можете использовать предоставленный метод guess для проверки догадки со следующей сигнатурой int guess(int num).

Метод возвращает следующие результаты:

-1 если ваша догадка больше, чем выбранное мной число;
1 если ваша догадка меньше выбранного мной числа;
0 если ваша догадка равна выбранному мною числу.

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

Ограничения #

Загадываемое число всегда находится в диапазоне от 1 до 2³¹ - 1

Примеры #

Исходные данные: n = 10, загадано число 6

Ответ: 6
Исходные данные: n = 1, загадано число 1

Ответ: 1
Исходные данные: n = 2, загадано число 1

Ответ: 1

Решение #

Это классическая задача, которая решается при помощи бинарного поиска.

Нам нужно итеративно выполнять несколько шагов.

Найти крайнюю левую и правую границы интервала, то есть 1 и n соответственно.
Найти середину этого интервала и проверить полученное число:

если полученное число больше загаданного, то правую границу нужно сместить на mid - 1;
если полученное число меньше загаданного, то левую границу нужно сместить на mid + 1;
если полученное число равно загаданному, то мы нашли ответ.

Этот алгоритм нужно повторять до тех пор, пока мы не найдем ответ или пока левая и правая границы не пересекутся.

Реализация #

package guess_number_higher_or_lower

var guess func(num int) int

func guessNumber(n int) int {
	left := 1
	right := n

	for left <= right {
		mid := (left + right) / 2
		res := guess(mid)

		if res == 0 {
			return mid
		} else if res == 1 {
			left = mid + 1
		} else {
			right = mid - 1
		}
	}

	return 0
}

// Для реализации примера функция принимает в качестве параметра функцию guess.
// В задаче на leetcode это функция предоставляется как API.
export const guessNumber = (n: number, guess: (num: number) => number): number => {
    let left = 1
    let right = n

    while (left <= right) {
        const mid = Math.floor((left + right) / 2)
        const res = guess(mid)

        if (res === 0) {
            return mid
        } else if (res === 1) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }

    return 0
}

Оценка сложности #

По времени

O(log₂ n) так как мы перебираем диапазон чисел бинарным поиском.

По памяти

0(1) так как мы не выделяем дополнительной памяти.

Оригинал задачи на Leetcode

Algorithmics