Бинарный поиск
В этой беседе излагаются некоторые соображения по части бинарного поиска. Предполагается, что зритель знаком с основной идеей двоичного поиска, так как это не учебное видео, а изложение своего опыта.
- Показаны некоторые изящные реализации алгоритма.
- Выполнено сравнение реализаций.
- Показаны типичные ошибки и то, как их можно избежать.
- Приводятся некоторые рассуждения о том, что может быть быстрее бинарного поиска.
В видео используются ссылки на следующие источники:
- Мой основной блог
http://zealcomputing.ru
- Архив с программой и презентацией
https://yadi.sk/d/U3tWgcVEmFXCw
- Измерение времени работы программы
http://codeforces.com/blog/entry/4030#comment-81711
- Некоторые полезные структуры данных для поиска
https://en.wikipedia.org/wiki/Fusion_tree
https://en.wikipedia.org/wiki/X-fast_trie
https://en.wikipedia.org/wiki/Y-fast_trie
- Только 10% программистов способны написать двоичный поиск
http://habrahabr.ru/post/91605/
- Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken
http://googleresearch.blogspot.ru/2006/06/extra-extra-read-all-about-it-nearly.html
- World’s Fastest Binary Search?
http://eigenjoy.com/2011/01/21/worlds-fastest-binary-search/
- Показаны некоторые изящные реализации алгоритма.
- Выполнено сравнение реализаций.
- Показаны типичные ошибки и то, как их можно избежать.
- Приводятся некоторые рассуждения о том, что может быть быстрее бинарного поиска.
В видео используются ссылки на следующие источники:
- Мой основной блог
http://zealcomputing.ru
- Архив с программой и презентацией
https://yadi.sk/d/U3tWgcVEmFXCw
- Измерение времени работы программы
http://codeforces.com/blog/entry/4030#comment-81711
- Некоторые полезные структуры данных для поиска
https://en.wikipedia.org/wiki/Fusion_tree
https://en.wikipedia.org/wiki/X-fast_trie
https://en.wikipedia.org/wiki/Y-fast_trie
- Только 10% программистов способны написать двоичный поиск
http://habrahabr.ru/post/91605/
- Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken
http://googleresearch.blogspot.ru/2006/06/extra-extra-read-all-about-it-nearly.html
- World’s Fastest Binary Search?
http://eigenjoy.com/2011/01/21/worlds-fastest-binary-search/
