Допустим, что вы вводите свои данные при входе на Facebook. При этом Facebook необходимо проверить, есть ли у вас учетная запись на сайте. Для этого ваше имя пользователя нужно найти
в базе данных. Допустим, вы выбрали себе имя пользователя “karlrnageddon”.
Facebook может начать искать с буквы А и проверять все подряд, но разумнее будет начать с середины.
Перед нами типичная задача поиска. И во всех этих случаях для решения задачи можно применить один алгоритм: бинарный поиск.
Бинарный поиск – это алгоритм; на входе он получает отсортированный список элементов (позднее я объясню, почему он должен быть отсортирован). Если элемент, который вы ищете, присутствует в списке, то бинарный поиск возвращает ту позицию, в которой он был найден. В противном случае бинарный поиск возвращает null
Пример
Рассмотрим пример того, как работает бинарный поиск. Сыграем в простую игру: я загадал число от 1 до 100.
Предположим, вы начинаете перебирать все варианты подряд: 1, 2, 3, 4…
При каждой догадке исключается только одно число. Если я загадал число 99, то , чтобы добраться до него, потребуется 99 попыток!
Более эффективный поиск
Существует другой, более эффективный способ. Начнем с 50.
Слишком мало … но вы только что исключили половину чисел! Теперь вы знаете, что все числа 1-50 меньше загаданного. Следующая попытка: 75.
С бинарным поиском вы каждый раз загадываете число в середине диапазона и исключаете половину оставшихся чисел.
В общем случае для списка из n элементов бинарный поиск выполняется за log2n шагов, тогда как простой поиск будет выполнен за n шагов. Бинарный поиск это “сколько раз можно делить диапазон пополам, пока не останется 1 элемент”. Но математика та же, потому что это про степени двойки.
Для n = 100:
- log2(100) это число, x, такое что 2^x = 100
- примерно: log2(100) ≈ 6.64
А по шагам (целыми сравнениями):
- 2^6 = 64 (мало)
- 2^7 = 128 (уже достаточно)
Значит нужно максимум 7 шагов (сравнений), чтобы найти элемент (или понять, что его нет) в списке из 100 элементов, если он отсортирован.
Для сравнения: линейный поиск в худшем случае до 100 шагов.
Пример
Функция binary_search получает отсортированный массив и значение. Если
значение присутствует в массиве, то функция возвращает его позицию. При
этом мы должны следить за тем, в какой части массива проводится поиск.
Вначале это весь массив:
low = 0
high = len(list) - 1 
Каждый раз алгоритм проверяет средний элемент:
mid = (low + high)/2 // Если значение {low+high) нечетно, то Python автоматически округляет значение mid в меньшую сторону
guess = list[mid] Если названное число было слишком мало, то переменная low обновляется
соответственно – мы его увеличиваем. Теперь 1-й указатель стоит на начале второй половины массива:
if guess < item :
low = mid + 1 
А если догадка была слишком велика, то обновляется переменная high. Полный
КОД ВЫГЛЯДИТ так:
def binary_search(list, item):
# В переменных low и high хранятся границы
# той части списка, в которой выполняется поиск
low = 0
high = len(list) - 1
# Пока эта часть не сократится до одного элемента...
while low <= high:
# ...проверяем средний элемент
mid = (low + high) // 2
guess = list[mid]
# Значение найдено
if guess == item:
return mid
# Много - ищем в левой половине
if guess > item:
high = mid - 1
# Мало - ищем в правой половине
else:
low = mid + 1
# Значение не существует
return None
# А теперь протестируем функцию!
my_list = [1, 3, 5, 7, 9]
# Вспомните: нумерация элементов начинается с 0.
# Второй ячейке соответствует индекс 1
print(binary_search(my_list, 3)) # => 1
# "None" в Python означает "ничто".
# Это признак того, что элемент не найден
print(binary_search(my_list, -1)) # => NoneЗадача: найти Имя в массиве
<?php
$names = [
"Александр",
"Анастасия",
"Андрей",
"Анна",
"Артём",
"Виктория",
"Владимир",
"Дарья",
"Дмитрий",
"Евгений",
"Екатерина",
"Елена",
"Иван",
"Ирина",
"Кирилл",
"Ксения",
"Максим",
"Мария",
"Михаил",
"Наталья",
"Никита",
"Ольга",
"Павел",
"Полина",
"Сергей",
"Светлана",
"Татьяна",
"Юлия"
];
function findName($names, $name) {
/* указатели на 1-й и последний элемент в массиве*/
$low = 0;
$high = count($names) - 1; // 27
while ($low <= $high) {
/*берем имя по центру*/
$mid = floor(($low + $high) / 2); // 13
if ($names[$mid] == $name) {
return $mid;
}
if ($names[$mid] < $name) {
/*ищем во второй половине массива*/
$low = $mid + 1; // 14
}
if ($names[$mid] > $name) {
/*ищем в первой половине массива*/
$high = $mid - 1; // 12
}
}
return null;
}
$result = findName($names, 'Дарья');
var_dump($result); // 7Вариант с рекурсией
Рекурсия в PHP — это прием программирования, при котором функция вызывает саму себя.
Любая рекурсивная функция должна иметь два компонента:
- Условие выхода (базовый случай): точка, где вызовы прекращаются. Без неё возникнет бесконечный цикл и ошибка переполнения стека.
- Рекурсивный шаг: вызов функцией самой себя с измененными аргументами.
<?php
$names = [
"Александр",
"Анастасия",
"Андрей",
"Анна",
"Артём",
"Виктория",
"Владимир",
"Дарья",
"Дмитрий",
"Евгений",
"Екатерина",
"Елена",
"Иван",
"Ирина",
"Кирилл",
"Ксения",
"Максим",
"Мария",
"Михаил",
"Наталья",
"Никита",
"Ольга",
"Павел",
"Полина",
"Сергей",
"Светлана",
"Татьяна",
"Юлия"
];
function recursiveFindName($names, $name, $low, $high) {
/*выходим с функции*/
if ($low > $high) return null;
var_dump('Low: ' . $low);
var_dump('High: ' . $high);
/*берем имя по центру*/
$mid = floor(($low + $high) / 2); // 13
if ($names[$mid] == $name) {
/*Нашли*/
return $mid;
}
if ($names[$mid] < $name) {
/*ищем во второй половине массива*/
$low = $mid + 1; // 14
return recursiveFindName($names, $name, $low, $high);
}
if ($names[$mid] > $name) {
/*ищем в первой половине массива*/
$high = $mid - 1; // 12
return recursiveFindName($names, $name, $low, $high);
}
}
$result = recursiveFindName($names, 'Ольга', 0, count($names) - 1);
var_dump($result); // 21Вот для наглядности логируем как менялись индексы указателей.
string(6) "Low: 0"
string(8) "High: 27"
string(7) "Low: 14"
string(8) "High: 27"
string(7) "Low: 21"
string(8) "High: 27"
string(7) "Low: 21"
string(8) "High: 23"
string(7) "Low: 21"
string(8) "High: 21"
float(21)Почему мы возвращаем функцию, а не вызываем ее?
return recursiveFindName($names, $name, $low, $high);Наша функция возвращает результат, только если мы нашли то, что искали либо null.
function recursiveFindName($names, $name, $low, $high) {
/*выходим с функции*/
if ($low > $high) return;
....
if ($names[$mid] == $name) {
/*Нашли*/
return $mid;
}
А если на текущей итерации не нашли, то return говорит: “верни то, что вернёт следующий вызов”. Это как передать эстафетную палочку обратно по цепочке 🏃♂️🏃♂️🏃♂️
Текущая итерация говорит: “мой результат = результат следующего вызова”. Она как бы делегирует ответ дальше по цепочке.
По сути говорим: “на текущей итерации не получилось вернуть результат, давай поменяем аргументы, снова вызовем функцию и может она тогда вернет нужный результат“.
И только последняя итерация (которая нашла элемент или дошла до $low > $high) возвращает конкретное значение — индекс или null. А все предыдущие просто передают это значение наверх.
вызов 1: return recursiveFindName(...) // ждёт результат от вызова 2
вызов 2: return recursiveFindName(...) // ждёт результат от вызова 3
вызов 3: return 21 // нашли!
вызов 2: получил 21, возвращает 21
вызов 1: получил 21, возвращает 21Итог:
Каждый вызов рекурсии либо:
- возвращает готовый ответ (нашёл / не нашёл)
- либо делегирует задачу следующему вызову с уточнёнными параметрами
