Бинарный поиск против простого поиска
Согласно книгам по алгоритмам, производительность бинарного поиска составляет O (log n), а для простого поиска - O (n).
Но почему бы нам также не принять во внимание время, затрачиваемое на сортировку, которая является необходимым условием для бинарного поиска?
Ответы 2
Предполагается, что данные будут храниться уже отсортированными. Поскольку данные не нужно пересортировать каждый раз при выполнении поиска, они не учитываются в Big O.
Вкратце: потому что обычно создание этого списка выполняется только один раз, тогда как поиск (и обновление) выполняется несколько раз.
Для построения отсортированного списка действительно требуется O (n журнал n). Смысл использования бинарного поиска заключается в том, что после сортировки коллекции мы можем выполнять запросы несколько к этому списку, каждый с О (журнал п).
Кроме того, если вы используете, например, двоичное дерево поиска, вы также можете выполнять вставку и удаление элементов в О (журнал п), поэтому обновление коллекция также может быть дешевой (при условии, что вы используете для этого эффективную структуру данных).
Например, в базе данных часто используются индексы для быстрого поиска. Обычно количество чтений велико по сравнению с количеством обновлений. Для обновления одного элемента требуется О (журнал п), поэтому создание индекса для существующих данных действительно дорого, но это не очень распространено по сравнению с поиском и обновлением Структура данных B-дерево [вики].
Двоичный поиск принимает это как предварительное условие. Идея состоит в том, что вы сортируете список/массив однажды, а затем можете выполнять поисковые запросы несколько.