Сложность: easy
Мы играем в игру "Угадай число" от 1 до n.
Есть предопределённая функция guess(int num), которая возвращает:
-1 — если num больше загаданного числа
1 — если num меньше загаданного числа
0 — если num совпадает с загаданным числом
Пример:
Input: n = 10, pick = 6
Output: 6
👨💻 Алгоритм:
1⃣Применяем бинарный поиск для нахождения загаданного числа. Начинаем с числа, расположенного в середине диапазона. Передаем это число функции guess.
2⃣Если функция guess возвращает -1, это означает, что загаданное число меньше предположенного. Продолжаем бинарный поиск в диапазоне чисел, меньших данного.
3⃣Если функция guess возвращает 1, это означает, что загаданное число больше предположенного. Продолжаем бинарный поиск в диапазоне чисел, больших данного.
😎 Решение:
class Solution extends GuessGame {
function guessNumber($n) {
$low = 1;
$high = $n;
while ($low <= $high) {
$mid = $low + intdiv($high - $low, 2);
$res = guess($mid);
if ($res == 0)
return $mid;
else if ($res < 0)
$high = $mid - 1;
else
$low = $mid + 1;
}
return -1;
}
}Ставь 👍 и забирай 📚 Базу знаний