Есть один такой карточный фокус — выбираете из колоды 15 карт и просите человека загадать любую из них. Затем выкладываете карты по очереди в 3 стопки по одной (1-я карта — в первую стопку, 2-я — во вторую, 3-я — в третью, 4-я — в первую и т.д.), предварительно попросив «испытуемого» следить, в какую стопку попадёт загаданная карта.
Когда получится 3 стопки по 5 карт — спросите, в какой из стопок лежит загаданная карта. Получив ответ, возьмите эту стопку и положите посередине между двумя другими стопками.
Повторите вышеописанную процедуру ещё раз, не перемешивая колоду: также выкладывайте карты по одной в три стопки, а после получения ответа о том, в какой из стопок лежит нужная карта, положите эту стопку посередине между двумя другими, чтобы снова в вашей руке оказалось 15 карт. Снова не перемешивайте!
Выложите раскладку в третий раз, задав тот же вопрос и получив ответ. После третьей раскладки вы уже будете знать загаданную карту — она будет третьей по счёту в указанной стопке из пяти карт (то есть ровно в центре стопки).
Далее уже дело за вашей фантазией — зная загаданную карту, её можно как-нибудь эффектно вытащить из колоды. 😎
Этот фокус напоминает один из алгоритмов программирования — бинарный поиск. Хоть сам алгоритм в фокусе и другой, но в бинарном поиске мы тоже «сужаем выборку», чтобы найти нужное значение.
Что за бинарный поиск?
Попросите человека загадать число от 1 до 100 и записать его, например, на листе бумаги. Условие отгадывания при этом будет такое: вы называете число, а загадавший будет говорить «больше», если загаданное число больше названного вами, «меньше» — если число меньше. Ну и, конечно, «угадал» — если угадали.
И самое интересное — сообщите загадавшему, что вы отгадаете число не больше, чем за 7 попыток!!!
Итак, попытка номер 1. 🙂
Мы имеем диапазон возможных загаданных чисел от 1 до 100. Давайте сократим его вдвое. Предположите, что человек загадал число 50.
Попытка номер 2.
Получив ответ «больше» или «меньше», мы тут же вдвое облегчаем себе задачу. Например, нам ответили «меньше».
Делим в уме 50 на 2 и предполагаем, что загаданное число — 25. На этот раз получаем ответ, например, «больше». И снова мы вдвое сократили себе область поиска!
Попытка номер 3.
Теперь мы знаем, что загаданное число находится где-то между 25 и 50. Нам надо поделить оставшийся диапазон на два и найти его центр:
- (50-25) / 2 = 13 (округляем по правилам математики 12,5 до 13)
- 25 + 13 = 38 (число, находящееся примерно посередине между 25 и 50)
Да, придётся немного посчитать в уме, но оно того стоит! 🙂
На предположение, что загаданное число 38, мы получаем ответ «меньше». Значит, загаданное число находится между 25 и 38.
Попытка номер 4.
Всё так же, как и раньше.
(38-25) / 2 = 7 (округлённо)
25 + 7 = 32
Попытка номер 5.
Получаем ответ «больше»! Загаданное число находится между 32 и 38 (как и ранее, не включая эти числа, что логично). У нас осталось всего-ничего вариантов: 33, 34, 35, 36, 37 и целых три попытки! 😉
Снова загадываем число посередине диапазона, то есть 35 (здесь уже считать даже в уме довольно-таки легко).
Попытка номер 6.
Ну, допустим, в этот раз снова «больше». Загаданное число — это либо 36, либо 37. Тут уже можете выбирать любое из двух для отгадывания, ведь у вас 2 попытки на отгадывание одного числа из двух!!! 😁
Однако давайте продолжим следовать алгоритму: (38-35) / 2 = 2 (округляя 1,5 до 2); 35 + 2 = 37.
Попытка номер 7.
Вероятность угадать число в предыдущей попытке уже была неплохой — 50%. Но, предположим, что нам не повезло. У нас есть ещё 1 попытка, чтобы отгадать число. Из оставшихся вариантов только 36, его и угадываем. 🙂
Не исключено, что мы могли угадать число гораздо раньше, если человек загадал одно из чисел в серединах диапазонов. Также не исключено, что без использования алгоритма вы сможете угадать число быстрее чисто рандомно, но зато алгоритм гарантирует, что вы выполните задачу, не превышая оговоренное количество попыток!
Чем же крут алгоритм бинарного поиска?
А тем, что при увеличении диапазона загадываемых чисел, например, в 10 раз (то есть со 100 до 1000), количество требуемых попыток не увеличится в 10 раз с 7 до 70, а составит всего 10 попыток, то есть всего на 3 попытки больше! Представляете, как можно впечатлить человека, не знающего алгоритм бинарного поиска! 😁
Он загадает число от 1 до 1000, а вы отгадаете не более, чем за 10 попыток!!! Правда, придётся изрядно попотеть при расчётах в уме. Хотя… Отгадывающий может взять калькулятор для расчётов, но, согласитесь, будет уже не так эффектно. 🙂
В чём магия?
Всё просто: количество попыток для нахождения числа в диапазоне зависит от степени числа 2 (ведь мы всё время сокращаем выборку вдвое). Чтобы это всё не вспоминать — ниже есть таблица степеней числа 2 (до 13-й степени).
| Степень | Результат |
| 2 | 4 |
| 3 | 8 |
| 4 | 16 |
| 5 | 32 |
| 6 | 64 |
| 7 | 128 |
| 8 | 256 |
| 9 | 512 |
| 10 | 1024 |
| 11 | 2048 |
| 12 | 4096 |
| 13 | 8192 |
Короче, если у вас диапазон от 1 до 100, то 7 попыток всегда хватит, потому что 100 меньше 128. Так же и для диапазона от 1 до 5000 потребуется 13 попыток, ведь 5000 меньше 8192.
Вот такой вот классный алгоритм! А в реальной жизни мы его используем, например, если требуется найти что-то в словаре или энциклопедии. Чтобы найти какое-нибудь слово на букву «К», мы интуитивно откроем книгу где-то посередине и посмотрим, слова на какую букву там будут идти. Дальше будем уже листать вперёд или назад, в зависимости от увиденного.
Ну и, конечно, в программировании это тоже используется. Например, для поиска пользователей на сайте. Да, там может быть не чистый бинарный поиск, а несколько другие, более сложные алгоритмы, но принцип будет очень похожим.
В качестве бонуса приведу пример кода алгоритма бинарного поиска на одном из моих любимых языков программирования — да, мои вкусы специфичны. 🙂
<script>
let test_array = [-20, 5, 10, 19, 54, 65, 77, 95];
let search = function(nums, target) {
let left = 0;
let right = nums.length - 1;
let mid;
while(left <= right) {
mid = Math.round((right - left) / 2) + left;
if (target === nums[mid]) return mid;
else if (target < nums[mid]) right = mid - 1;
else left = mid + 1;
}
return -1;
}
console.log(search(test_array, 10));
</script>Оставить комментарий к этой статье можно в нашем Telegram-канале:
Присоединяйтесь! 😉