Почему двоичный поиск, требующий отсортированных данных, считается лучше линейного поиска?

Question

Я всегда слышал, что линейный поиск — это наивный подход, а бинарный поиск лучше его по производительности из-за лучшей асимптотической сложности.Но я никогда не понимал, чем он лучше линейного поиска, когда перед двоичным поиском требуется сортировка?

Линейный поиск O(n) и двоичный поиск O(log n).Кажется, это является основанием для утверждения, что бинарный поиск лучше.Но двоичный поиск требует сортировки, которая O(n log n) за лучшие алгоритмы.Таким образом, двоичный поиск не должен быть быстрее. как требуется сортировка.

Я читаю CLRS, в котором автор подразумевает, что при сортировке вставкой вместо использования наивного подхода линейного поиска лучше использовать двоичный поиск для поиска места, куда необходимо вставить элемент.В данном случае это кажется оправданным, поскольку на каждой итерации цикла существует отсортированный список, к которому можно применить бинарный поиск.Но в общем случае, когда нет никакой гарантии относительно набора данных, в котором нам нужно искать, не является ли использование двоичного поиска на самом деле хуже, чем линейный поиск, из-за требований сортировки?

Есть ли какие-либо практические соображения, которые я упускаю из виду, которые делают бинарный поиск лучше линейного?Или бинарный поиск считается лучше, чем линейный поиск, без учета времени вычислений, необходимого для сортировки?

Answer 1

Есть ли какие-либо практические соображения, которые я упускаю из виду, что делает двоичные поиски лучше, чем линейный поиск?

Да - вы должны сделать только один раз, а затем вы можете сделать двоичный поиск o (log n), как вы хотите, тогда как линейный поиск o (n) каждый раз.

Конечно, это только преимущество, если вы действительно выполняете несколько поисков на одни и те же данные.Но «писать один раз, читать часто» сценарии довольно распространены.

Answer 2

Основное предположение в том, что вы не делаете один поиск.

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

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

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

Когда вам нужно разобраться каждый раз перед поиском нет никаких преимуществ.

Примечание. Обратите внимание, что есть алгоритмы сортировки, которые очень быстро, когда список уже отсортирован (или почти отсортирован).Большинство определений эффективности ожидают несоответствующего списка.

Answer 3

потому что, как только у вас есть отсортированный список, вам не нужно каждый раз пересортировать его, а это означает, что если у вас больше O(log n) поисковых запросов, предварительная сортировка принесет вам выигрыш (O(n log n + k log n) против O(k*n)

Answer 4

Представьте себе два телефонных книги.

Одна телефонная книга имеет имена в алфавитном порядке.Чтобы найти запись, которую вы хотите, вы открыты в середине, проверьте запись, затем двигайтесь вперед или назад в зависимости от того, не ходатайствуете ли вы или поднял.

Другое телефонная книга имеет имена в случайном порядке.Чтобы найти нужный ввод, вы начинаете в начале и продолжаете, пока не найдете то, что вы хотите.

будет работать вторая книга в любом разумно размеренном городе?

Answer 5

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

Answer 6

Как и многие другие ответили, двоичный поиск действительно предпочтительнее, потому что этап сортировки может быть выполнен только один раз, и фактический поиск может быть выполнен столько раз, сколько понравится. Однако для определенных значений N (то есть определенные размеры ввода), двоичный поиск - всегда больше выполнения, чем линейный поиск (даже за один запуск).

«Точка перескакивания» рассчитывается путем решения асимптотической уравнения сложности:

n log n + log n = n

.

Как вы можете Эта интересная статья Пробник, который включает в себя несколько приятных измерений глубины производительности на текущих процессорах:

Если вам нужно обыскить через отсортированный массив целых чисел и Производительность действительно, действительно важно, использовать линейный поиск, если ваш Массив находится ниже около 64 элементов в размерах, бинарный поиск, если это выше.

Answer 7

в словах Лэймана:

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

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

Answer 8

В то время как много веских причин для «двоичного поиска лучше» уже перечислены, мы также могли бы посмотреть на преимущества с точки зрения пользователя:

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