Бинарный поиск

[buti]

Предлагаю обсудить следующую видео-лекцию, касающуюся написания правильного бинарного поиска.

В этой беседе излагаются некоторые соображения по части бинарного поиска. Предполагается, что зритель знаком с основной идеей двоичного поиска, так как это не учебное видео, а изложение своего опыта.

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

В видео используются ссылки на следующие источники:

• Сайт проекта
  
• Архив с программой и презентацией
  
• Измерение времени работы программы
  
• Некоторые полезные структуры данных для поиска
  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?

Какие ещё моменты стоило упомянуть в лекции? С чем вы согласны или не согласны? Полезна ли была лекция?

[aa_dav]

Такие вещи надо делать в виде текста.
Видеолекции крайне неудачный формат как для самого процесса обучения, так и поисковой оптимизации, так и копирование кусков кода, и так далее.

[NT2000]

Одно другому не помеха.
Я бы предложил дополнить видео-лекции текстовым изложением + подробные примеры.

[Pavia]

buti
1) Много лишних слов, что только отвлекает.
2) По поводу правильности написания. Насколько помню были ошибки округления. Эта история идёт с журнала ACM где в первые был опубликован алгоритм бинарного поиска, и спустя время был опубликован правильный алгоритм.
3) По поводу скорости, не рассмотрен классический прием инвертирования индекса, для ускорения поиска. При этом ускорение достигается за счёт оптимизации работы кэша.

[buti]

Спасибо за замечания, мы их обязательно обдумаем.

[buti]

Цитата:

так и копирование кусков кода,

По ссылкам всегда приводится текст презентации и код программы.