Угадай число

Сегодня мы рассмотрим вместе с вами еще одну классическую задачу из учебников.

Сложность: 🟢 Легкая

ℹ️ Описание

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

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

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

int guess(int num)

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

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

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

⚠️ Ограничения

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

1️⃣ Пример

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

Ответ: 6

2️⃣ Пример

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

Ответ: 1

3️⃣ Пример

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

Ответ: 1

✅ Решение

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

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

1. Найти крайнюю левую и правую границы интервала, то есть 1 и n соответственно.
2. Найти середину этого интервала и проверить полученное число:
— если полученное число больше загаданного, то правую границу нужно сместить на mid - 1;
— если полученное число меньше загаданного, то левую границу нужно сместить на mid + 1;
— если полученное число равно загаданному, то мы нашли ответ.

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

Посмотреть реализацию в блоге

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

По времени

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

По памяти

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

#binary_search