#c #algorithm #search #data-structures
Вопрос:
Почему мы вообще говорим, что двоичный поиск (BS) лучше, чем линейный поиск (LS)? Например, когда я передаю несортированный массив в BS и LS. Нам нужно разобраться на предмет BS. Временная сложность всех встроенных алгоритмов сортировки составляет не менее O(nlogn). Таким образом, общая трудоемкость сортировки и поиска составляет O(nlogn logn)=O(nlogn). В качестве BS возьмем O(logn). В то время как LS требуется только O(n), чтобы найти элемент. Таким образом, в соответствии с этим утверждением LS лучше, чем BS, для поиска элемента в списке.
Комментарии:
1. Двоичный поиск имеет сложность O(logn), когда входные данные уже отсортированы , и многие варианты использования дают отсортированные результаты, поэтому двоичный поиск весьма полезен
2. Никто не утверждает, что BS хорош в несортированном массиве, по крайней мере, до тех пор, пока вы выполняете только 1 поиск, а не просматриваете массив снова и снова, и в этот момент первоначальная сортировка, возможно, была лучшей идеей.
3. Вы не можете выполнять двоичный поиск по несортированным данным. Ну, вы можете попробовать, но результаты, скорее всего, будут неоднозначными :-). Именно сортировка позволяет решить, какую половину пространства решений выбрасывать на каждой итерации. Например, если вы ищете 42, а средний элемент равен 20, как вы можете узнать, находится ли 42 в первой или второй половине, если данные несортированы?
Ответ №1:
Сортировка и использование двоичного поиска имеет смысл, когда вам нужно выполнить несколько поисков в одном массиве.
Пусть стоимость одного линейного поиска равна a.N стоимости сортировки b.N.lg(N) и стоимости двоичного поиска c.Lg(N) .
Теперь вы сравниваете M.a.N с b.N.lg(N) M.c.lg(N) для M поиска. Точка безубыточности находится на
M = b.N.lg(N) / (a.N - c.lg(N)) ≈ b.lg(N)/a