В этой беседе излагаются некоторые соображения по части бинарного поиска. Предполагается, что зритель знаком с основной идеей двоичного поиска, так как это не учебное видео, а изложение своего опыта.
- Показаны некоторые изящные реализации алгоритма.
Выполнено сравнение реализаций. - Показаны типичные ошибки и то, как их можно избежать.
- Приводятся некоторые рассуждения о том, что может быть быстрее бинарного поиска.
В видео используются ссылки на следующие источники:
- Архив с программой и презентацией
- Измерение времени работы программы
- Некоторые полезные структуры данных для поиска
Fusion tree, X-fast trie, Y-fast_trie - Только 10% программистов способны написать двоичный поиск
- Extra, Extra — Read All About It: Nearly All Binary Searches and Mergesorts are Broken
- World’s Fastest Binary Search?