Лучший алгоритм поиска // Vital Math

Бинарный поиск – простой, но мощный алгоритм поиска в упорядоченном массиве. Но несмотря на свою простоту, всего 10% программистов смогут написать его без ошибок. Как же работает алгоритм? В чем его сложность? Где он применяется? И чем очень полезен в повседневной жизни?

Пересказ видео “Бинарный поиск”

Вступление:

Видео начинается с вопроса: как быстро найти нужную книгу в огромной библиотеке, где все книги не расставлены по алфавиту?

Предлагаются два неэффективных метода:

Просматривать все книги по порядку (затратно по времени, особенно если нужная книга находится в конце).
Случайным образом выбирать книги (шанс найти нужную книгу мал).

Предлагается более эффективный метод – бинарный поиск.

Суть бинарного поиска:

Алгоритм делит массив пополам на каждом шаге.
Сравнивается искомое число с "средним" числом в массиве.
Если искомое число меньше "среднего", то поиск продолжается в левой половине массива.
Если искомое число больше "среднего", то поиск продолжается в правой половине массива.
Процесс повторяется, пока не будет найдено искомое число или не станет ясно, что его нет в массиве.

Преимущества бинарного поиска:

Эффективность: В худшем случае для поиска элемента в массиве из N элементов требуется log2(N) сравнений, что значительно меньше, чем N сравнений, необходимых для линейного поиска.
Простота: Алгоритм прост для понимания и реализации.
Универсальность: Может использоваться для поиска различных типов данных (числа, строки, объекты) в упорядоченных массивах.

Пример реализации бинарного поиска:
Python

def binary_search(array, target):
low = 0
high = len(array) – 1

while low <= high:
mid = (low + high) // 2
if array[mid] == target:
return mid
elif array[mid] < target:
low = mid + 1
else:
high = mid – 1

return -1

Используйте код с осторожностью.

Ошибки при реализации бинарного поиска:

Переполнение целых: Необходимо учитывать ограничения типов данных при вычислении индекса среднего элемента.
Неверные границы поиска: Убедитесь, что границы поиска правильно инициализированы.
Неверные условия окончания поиска: Убедитесь, что цикл поиска корректно завершается.
Неверные условия при отсутствии элемента: Определите, как алгоритм должен вести себя, если искомый элемент не найден.

Приложения бинарного поиска:

Поиск элементов в массивах: Используется в различных приложениях, таких как сортировка, поиск слов в словаре, поиск файлов на компьютере.
Реализация алгоритмов: Используется в более сложных алгоритмах, таких как слияние сортировки, быстрая сортировка.
Игры: Используется в играх для поиска объектов на игровом поле или определения оптимальных ходов.

Заключение:

Бинарный поиск – это мощный и эффективный алгоритм, который имеет множество практичных применений.

Задание:

Автор видео предлагает попробовать написать свой код бинарного поиска и отправить ему на проверку.

Важно: Указать язык программирования, который используется.

Дополнительные материалы:

https://gemini.google.com

Расшифровка видео

Вступление
0:00
Всем привет это Виталий Как быстро
0:02
искать Представьте Вы заходите в
0:04
огромную библиотеку в которой кто-то
0:05
убрал все указатели но вы знаете что
0:08
книги расположены в алфавитном порядке
0:10
вопрос как найти нужную книгу можно
0:14
начать Сначала с буквы а и рассматривать
0:17
все книги по порядку Если вы например
0:19
ищете автора на букву ф то застрянет
0:22
надолго можно пойти в случайную сторону
0:24
вдруг вам повезёт правда если как обычно
0:27
Тогда придётся опять случайно блуждать в
0:30
библиотеке несколько дней но оказывается
0:32
есть простой и очень эффективный способ
0:35
как найти нужную книгу способ который не
0:38
просто намного лучше А в сотни тысячи
0:40
миллионы раз лучше вместо дней блужданий
0:43
вы найдёте книгу за несколько шагов и
0:46
всё это благодаря простому но мощному
0:48
алгоритму алгоритму бинарного поиска в
0:52
его основе лежит тысячелетний принцип
0:53
разделяя власт то сам алгоритм будет
0:55
понятен даже ребёнку в нём два простых
0:57
шага код алгоритма всего 12 строчек и
1:00
при этом это мощнейший универсальный
1:02
алгоритм с огромным количеством
1:04
приложений что ещё более удивительно
1:05
несмотря на свою кажущуюся простоту 90%
1:09
программистов делают в нём ошибки что
1:11
это за алгоритм Почему он так эффективен
1:13
где он всё-таки применяется Почему 90%
1:16
программистов ошибаются и чему мы с вами
1:18
можем научиться у алгоритма для
1:20
повседневной жизни не забывайте
1:22
подписаться как всегда здесь мы
1:23
наслаждаемся красотой элегантностью
1:26
математики и её бесконечными
1:28
приложениями алгоритм бинарного поиска
1:35
[музыка]
Центральный университет
1:37
Поехали сегодня будет явно необычный
1:40
ролик на очень прикладную для математики
1:42
тему с алгоритмами информатикой
1:44
программированием всё это не только
1:46
красиво но и очень полезно в жизни
1:49
Помните я недавно рассказывал про
1:50
искусственный интеллект это одно из
1:52
ключевых событий этого Столетия уже
1:54
сейчас и ещё больше как мы скоро Увидим
1:58
в совсем недалёком будущем тоже всё
2:00
строится на математике компьютерных
2:02
науках и алгоритмах поэтому для тех кто
2:04
сейчас ищет не только числа в массиве но
2:06
и университет куда пойти учиться чтобы
2:08
получить прикладную специальность
2:10
полезную в настоящем и будущем хочу
2:12
рассказать про Центральный университет
2:14
что это за университет он создан при
2:17
партнёрстве тенков и других ведущих it
2:19
компаний Это полноценный университет с
2:22
кампусов в центре Москвы очм
2:24
образованием и дипломом ВУЗа
2:25
государственного образца более того это
2:27
первый в России частный ВУЗ на основе
2:30
так называемой стем модели это модель
2:32
образования при которой естественные
2:34
науки и инженерные предметы преподают в
2:36
связке друг с другом в конце учёбы
2:38
студенты готовят дипломный проект со
2:39
стажировкой в технологической компании
2:42
так Они получают опыт который
2:43
максимально приближен к будущей
2:45
профессии и будут готовы к полноценной
2:47
работе сразу после выпуска преподаватели
2:49
университета – это практики топовых it
2:51
компаний и эксперты ведущих мировых
2:54
университетов чему учат в центральном
2:57
университете в сентябре этого года
2:59
запускается первые программы
3:00
бакалавриата по направлениям разработка
3:03
искусственный интеллект бизнес аналитика
3:05
что важно сейчас есть возможность
3:08
получить грант чтобы учиться все 4 года
3:10
бесплатно или со скидкой до 75% Как
3:13
получить грант нужно зарегистрироваться
3:16
на конкурс и пройти отбор в конкурсе на
3:18
Гранты могут принять участие ученики
3:21
одиннадцатых классов и старших курсов
3:22
колледже зарегистрироваться на конкурс
3:25
можно по ссылке в описании А сам отбор
3:27
состоит из двух этапов тест не нужны
3:30
специальные знания достаточно школьной
3:31
программы и бизнес-игра по результатам
3:34
двух этапов определяется размер скидки
3:36
причём если не получилось пройти отбор с
3:38
первого раза Можно попробовать ещё
3:41
Количество попыток не ограничено конкурс
3:43
уже идёт каждый месяц комиссия выбирает
3:46
студентов которые получат Грант Поэтому
3:48
чем раньше Вы зарегистрируетесь тем
3:50
больше у вас шансов получить этот самый
3:52
Грант Не пропустите такой шанс и
3:54
Поделитесь новостью с другими переходите
3:56
по ссылке в описании и регистрируйтесь
3:58
на первый этап отбора как можно раньше
4:01
университет нашли Давайте вернёмся
4:03
теперь к бинарному
Бинарный поиск
4:09
поиску человек пытался упростить поиск
4:11
ещё за тысячи лет до компьютеров причём
4:13
одной из ключевых идей была сортировка
4:16
согласитесь найти слово в словаре
4:18
намного проще если слова упорядочены по
4:20
алфавиту на самом деле это простая идея
4:23
сейчас кажется очевидной но дойти до
4:24
этого для букв а не только чисел
4:27
человечеству удалось не сразу первый
4:29
пример длинного перечня упорядоченных
4:31
элементов Вавилонская Глиняная таблица
4:33
примерно ре века до нашей эры в этой
4:36
таблице изображено более 500 чисел в
4:38
шестеричной системе счислений и обратных
4:41
и величин отсортированных в
4:43
лексикографическом порядке то есть по их
4:45
буквенному написанию отсортировать 500
4:48
слов – это не такая уж и простая задача
4:50
часто слова упорядочивать только по
4:52
первым буквам или по первым двум
4:54
например в книгах о полоне софиста в I
4:56
веке нашей эры более сложные системы
4:59
появились лишь к середине прошлого
5:01
тысячелетия в 1604 году Роберт кодре
5:04
опубликовал первый словарь английского
5:06
языка с упорядоченным по алфавиту
5:08
словами хотя и большим количеством
5:10
ошибок но алгоритм поиска в
5:12
упорядоченном отсортированном массиве
5:14
появился намного позже лишь в 1946 году
5:17
американский физик Джон моч впервые
5:20
упомянул бинарный поиск в пятидесятых
5:22
годах метод стал хорошо известным в
5:24
научной среде но без какого-то
5:26
энтузиазма никто даже не пытался
5:28
придумать способ как работает алгоритм
5:30
для массивов длиной неравной степени
5:32
двойки наконец в начале шестидесятых
5:34
появился алгоритм бинарного поиска
5:36
который применим для любых размеров
5:39
массивов плюс появилось несколько
5:40
модификаций алгоритмов так родился
5:43
простой и мощный алгоритм поиска
5:45
работающий для отсортированных массивов
5:47
его ещё называют двоичным поиском или
5:50
методом деления пополам Но что же это за
5:53
алгоритм Давайте представим массив чисел
5:56
например 11 чисел отсортированных от
5:58
меньшего к большему и Допустим мы хотим
6:00
найти число
6:02
37 принцип алгоритма простой состоит из
6:05
двух действий на каждом шаге нужно найти
6:08
середину диапазона который сейчас
6:09
рассматриваем и убрать ту половину где
6:12
точно нет искомого числа Чтобы
6:14
продолжить поиск в оставшейся половине
6:17
Давайте попробуем найти число
6:19
37 в начале наш диапазон – это все 11
6:22
чисел середина – это шестое число слева
6:25
от него и справа от него по пять чисел
6:28
теперь смотрим на саму середину это
6:30
число 25 оно меньше чем то число которое
6:34
мы ищем значит это число и все числа
6:37
слева от числа 25 тем более не подходят
6:40
их можно сразу отбросить ответ нужно
6:42
искать во второй половине теперь Это наш
6:45
Новый диапазон ищем середину для него
6:49
это число 50 оно больше чем икома 37
6:53
поэтому можем спокойно откинуть это
6:55
число и правую половину нашего диапазона
6:58
где все числа больше п
7:00
ищем слева осталось всего два числа если
7:04
чисел чётное количество то для середины
7:06
диапазона обычно берётся округление в
7:08
нижнюю сторону в результате середина –
7:10
это число 37 и о чудо оно совпадает с
7:14
нашим искомым числом за три шага мы
7:17
нашли искомое число в массиве из Одина
7:20
чисел согласитесь звучит всё очень
7:22
просто разделяй и властвуй но только
7:25
Задумайтесь на каждом шаге Мы в два раза
7:28
упрощаем задачу выкидываю половину чисел
7:31
Если хотите увидеть алгоритм глазами
7:32
программистов Не пугайтесь вот так
7:34
всего-навсего выглядит 12 строчек кода
7:37
на питоне на вход подаётся массив И
7:40
искомый элемент задаются значения двух
7:42
указателей указатель левой границы
7:44
диапазона и правой границы в начальный
7:47
момент левая граница – это начало
7:49
массива а правая – последний элемент в
7:51
массиве затем начинаем цикл то есть
7:54
будем повторять дальнейшие шаги до тех
7:56
пор пока в рассматриваемом диапазоне
7:58
есть хотя бы один
8:00
э считаем индекс среднего элемента как
8:03
среднее между левым и правым указателями
8:06
если средний элемент меньше искомого то
8:08
выбрасываем левую половину то есть
8:09
обновляем левый указатель на начало
8:11
правой половины если средний элемент
8:14
больше искомого то оставляем левую
8:16
половину обновляем правый указатель а
8:18
иначе То есть если средний элемент равен
8:21
искомому мы его нашли поэтому возвращаем
8:23
номер найденного числа ура если же мы
8:26
прошли все шаги в диапазоне не осталось
8:28
элементо искомого числа просто нет в
8:30
массиве Поэтому возвращаем ми1 вот такая
8:34
простая функция хорошо скажете вы метод
8:36
понятен выглядит всё просто но что
8:38
такого особенного в этом простом
8:40
алгоритме оказывается только что вы
8:43
видели один из самых эффективных
8:44
алгоритмов поиска у которого есть много
8:47
интересных особенностей
Мощь и красота
8:52
Одной из самых впечатляющих рари
8:55
бинарного поиска являтся его эктив
8:59
других алгоритмов поиска в алгоритмах
9:02
сложность измеряется в количестве
9:03
операций в данном случае в числе
9:05
сравнений то есть сколько сравнений
9:07
одного числа с другим нужно сделать
9:08
чтобы наконец-то найти число в массиве
9:11
для линейного поиска нужно перебирать
9:13
все элементы по очереди и сравнивать
9:15
каждый с искомым элементом в лучшем
9:17
случае удастся найти нужное число за
9:19
одно сравнение если исходный элемент
9:22
совпадает с первым в худшим за
9:24
количество шагов равное длине массива в
9:27
нашем случае за 11 если число
9:30
последнее в таком случае если N – это
9:33
длина массива говорят что сложность
9:35
алгоритма порядка N или о большо от N но
9:39
посмотрите на бинарный поиск в худшем
9:41
случае мы будем уменьшать массив в два
9:44
раза пока не дойдём до одного элемента
9:46
то есть количество шагов равно степени в
9:49
которою нужно возвести два чтобы
9:51
получить длину массива примерно эта
9:53
степень равна двоичному логарифму от N
9:56
если бы точнее количество сравнений
9:58
равно двоично логарифму от N
10:03
округлённое – это порядок то есть
10:05
логарифм N а это оказывается не просто
10:09
намного а очень сильно лучше чем
10:11
сложность линейного поиска для больших
10:13
массивов Посмотрите на примере для
10:15
нашего уже любимого массива из
10:17
одиннадцати чисел в худшем случае для
10:19
линейного поиска нужно 11 сравнений а
10:21
для бинарного четыре то есть почти в три
10:24
раза лучше для тысячи чисел разница уже
10:27
100 раз
10:30
если чисел в массиве 1 млн для бинарного
10:32
поиска в худшем случае нужно всего 20
10:35
сравнений что в 50.000 раз лучше
10:37
линейного поиска а для 1 миллиарда как
10:40
думаете Сколько нужно бинарному поиску
10:43
30 сравнений против миллиарда для
10:46
линейного поиска можете себе представить
10:49
эти простые 12 строчек кода творят
10:51
чудеса бинарный поиск лучший алгоритм
10:54
поиска с точки зрения худшего или
10:55
среднего времени среди всех алгоритмов
10:57
основанных на сравнении чисел Кроме того
11:00
бинарный поиск решает задачи помимо
11:02
поиска заданного числа например
11:04
приближенный поиск Когда нужно найти
11:06
число которое отличается от заданного на
11:08
определённое значение так можно найти
11:11
первое ближайшее число к заданному или
11:13
первое меньшее чем заданное или второе
11:16
большее полезно когда ищешь в словаре не
11:18
только Точное слово но и очень близкое к
11:20
нему или ещё одна задача определить есть
11:24
ли число среди заданных или нет например
11:26
есть ли в библиотеке какая-то конкретна
11:29
книга среди миллиона других существует
11:32
ещё много модификаций бинарного поиска
11:34
например для массивов неограниченной
11:36
длины или двумерных массивов но Неужели
11:38
бинарный поиск настолько хорош что нет
11:40
алгоритмов лучше алгоритмы лучше есть
11:43
Правда они хороши для определённого типа
11:45
задач или структур данных Например если
11:47
данные представлены в виде определённой
11:49
структуры такой как деревья или хэш
11:51
таблиц для хэш таблиц в среднем время
11:53
поиска вообще Константа то есть какое-то
11:56
фиксированное число не зависящее От
11:58
длины массива но хэш таблицы оказываются
12:01
бесполезными для поиска например
12:03
следующего наибольшего числа для
12:05
заданного есть алгоритмы которые лучше
12:07
подходят для определённых задач например
12:09
для задачи определения наличия числа в
12:11
массиве но тем не менее алгоритм
12:14
бинарного поиска – это единственный
12:16
универсальный алгоритм который работает
12:18
всегда и даёт хороший результат намного
12:20
лучше линейного поиска Главное чтобы
12:23
массив был отсортирован а в основе лежит
12:26
всего-навсего простой принцип разделяй и
12:28
властвуй и 12 строчек кода Что может
12:31
быть Элегант но оказывается не всё так
12:33
просто этим простым алгоритмом
12:36
большинство программистов не могут
12:38
написать код бинарного поиска без
Ошибки в деталях
12:45
ошибок как писал один из величайших
12:48
компьютерных исследователей Дональд кнут
12:50
базовая идея бинарного поиска
12:52
относительно простая но детали могут
12:54
быть удивительно обманчиво ещё в 1986
12:58
году американский информатик дн бенли
13:00
опубликовал книгу по программированию
13:02
где поделился личным опытом бенли ВЛ
13:05
лекции для профессиональных
13:06
программистов ВМ и рассказывал про
13:08
бинарный поиск в какой-то момент он
13:10
давал задание студентам за 2 часа
13:12
написать код для алгоритма бинарного
13:14
поиска на любом языке программирования
13:17
Когда программисты сдавали работу Все
13:19
утверждали что уверены в своих
13:20
результатах после этого бенли проводил
13:23
разбор решений И какой вы думаете
13:26
результат несколько классов и более
13:28
сотни профес программистов но результат
13:30
был одинаковым Даже несмотря на огромное
13:32
количество времени на выполнение задания
13:34
у почти
13:36
90% Нашлись ошибки в коде более того в
13:39
самой книге Джона бенли в коде бинарного
13:42
поиска была ошибка которую заметили
13:44
только 20 лет спустя ошибки закрась даже
13:47
в языки программирования в Джаве ошибку
13:49
функции бинарного кода в одной из
13:51
библиотек никто не замечал почти 9 лет а
13:53
на Джаве на секундочку написано
13:55
программное обеспечение для баз данных
13:56
которые использует любая крупная
13:58
компания Ну что такого сложного в этом
14:01
простом алгоритме детали как верно
14:04
подметил Дональд нут например так
14:05
называемая проблема переполнения целых
14:07
чисел числа – это некоторый набор
14:09
символов в компьютере под число
14:11
выделяется определённое место или ячейки
14:13
памяти по простому Представьте что для
14:16
каждого числа выделяется 10 ячеек То
14:19
есть например такой компьютер может
14:21
работать с числами в которых не больше
14:22
десяти цифр поэтому большие числа в
14:25
которых более де цифр будут отображаться
14:27
некорректно Хотя програм может спокойно
14:29
продолжать работу Причём тут бинарный
14:32
поиск вспомните как мы считаем индекс
14:35
среднего элемента складываем указатель
14:37
начала диапазона и указатель конца и
14:39
делим на два но что Если сумма этих
14:42
чисел выходит за границу возможного даже
14:44
если каждый указатель допустимое число
14:46
сумма может быть больше допустимого и
14:48
появляется ошибка правда эту ситуацию
14:51
легко исправить если вспомнить
14:52
математику пятого класса и переписать
14:54
дробь как сумму левого указателя и разни
14:58
ме правыми и левыми указателями делённое
15:00
на два новая дробь – это число которое
15:03
точно лежит в рамках диапазона Так что
15:05
Никакой ошибки не возникает конечно для
15:07
разных языков программирования систем
15:09
всё работает по-разному например на
15:10
питоне такая ошибка не возникнет но
15:12
появится на Джаве Кроме того есть ещё
15:15
большое количество небольших неточностей
15:17
которые очень легко сделать и которые
15:19
могут привести к ошибкам для
15:20
определённых случаев например
15:22
неправильные границы поиска неверные
15:24
условия окончания поиска неверные
15:26
условия при отсутствии элемента бинарный
15:29
поск это хорошая проверка на
15:30
внимательность Так что вопрос к вам
15:33
Попробуйте на досуге написать свой код
15:35
бинарного поиска и прислать мне на почту
15:38
проверим точность ваших решений не
15:40
забудьте только написать для какого
15:41
языка программирования вы пишите хорошо
15:44
мы поняли если быть внимательным можно
15:47
написать мощный и эффективный алгоритм
15:49
для большого количества задач по поиску
15:51
Но где конкретно полезен алгоритм
15:54
бинарного поиска
Приложения
16:00
несмотря на свою простоту бинарного
16:02
поиска много по-настоящему практичных
16:04
приложений во-первых бинарный поиск
16:07
полезен Везде где есть упорядоченный
16:08
набор чисел слов символов электронные
16:11
словари энциклопедии телефонные
16:13
справочники базы данных планет и звёзд
16:15
хранение файлов на жёстком диске
16:17
компьютера фильтр товаров в
16:19
онлайн-магазине например Какие продукты
16:21
показать Когда вы ставите ограничения по
16:23
цене при выборе домашних тапочек в играх
16:26
финансах алгоритмах машинного обучения
16:28
для поиска гипер параметров в самом
16:30
программировании например для поиска
16:32
ошибок в коде если на каждом шаге
16:34
оставлять только ту часть кода Где
16:36
появляется баг можно быстро найти этот
16:38
Баг и конечно в Задачка на
16:40
собеседованиях Пишите внизу ваши любимые
16:43
задачи про бинарный поиск Кроме того
16:45
важен сам принцип деления пополам и
16:48
приоритизация на каждом шаге мы упрощаем
16:51
задачу в два раза похожим образом можно
16:54
искать не только числа но и корни
16:56
уравнения так называемый метод бисекции
16:58
об этом как-нибудь позже а сейчас пора
17:02
уже подвести небольшой
Три вывода
17:06
итог Какие три вывода можно сделать из
17:08
всей этой истории во-первых бинарный
17:11
поиск он же двоичный поиск или метод
17:13
деления пополам – это простой но мощный
17:16
алгоритм поиска элементов в
17:17
упорядоченном массиве на каждом шаге
17:19
нужно искать средний элемент и
17:21
сравнивать его с искомым если не
17:23
совпадает то продолжать искать только на
17:26
одной из Половин тем самым упрощая
17:28
задачу раза в результате бинарный поиск
17:30
в разы эффективнее простого линейного
17:32
поиска несмотря на свою простоту это
17:35
один из лучших А может просто лучший
17:37
алгоритм поиска программисты Пишите в
17:39
комментариях что думаете про бинарный
17:41
поиск и его эффективность во-вторых у
17:44
бинарного поиска простой принцип работы
17:47
но его сложно написать без ошибок в
17:49
алгоритме много нюансов и деталей таких
17:52
как переполнение целых чисел ошибки с
17:53
границами или условиями остановки
17:56
присылайте на почту ваши варианты
17:57
бинарного поиска смотрим сколько на
17:59
самом деле ошибок с кодом наконец В
18:02
третьих бинарный поиск очень полезный
18:05
алгоритм который применяется в большом
18:07
количестве приложений Везде где есть
18:09
упорядоченные значения можно
18:10
использовать бинарный поиск от
18:13
электронных энциклопедий до компьютерных
18:15
игр например Какие предметы нужно
18:18
загружать Когда Вы заходите в Новую
18:20
локацию Да и сам принцип в основе
18:22
бинарного поиска очень интересный найти
18:24
середину и отбросить половину значений
18:27
которые точно не являются решением на
18:29
каждом шаге мы разбиваем задачу на более
18:31
простые подзадачи и быстро находим ответ
18:34
пишите что думаете про бинарный поиск и
18:36
где Вы встречали его в реальной жизни
18:38
думайте и ищите решение проблем с
18:41
помощью бинарного поиска пока
18:47
[музыка]

Поделиться: