Big - O запись линейного и двоичного поиска

Question

В терминах записи Big - O линейный поиск - это a x^n, но что такое бинарный поиск? Я не на 100% уверен, что линейный поиск правильный.

Answer 1

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

Например, если у вас есть список с элементами [1, 3, 5, 7, 9, 11] и вы ищете 11, вы начнете с первого элемента, затем со второго элемента и так далее, что в этом случае займет 6 итераций.

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

Итак, мы говорим, что алгоритм линейного поиска O(n),

В случае бинарного поиска вы начинаете со среднего элемента списка:

• Случай 1: число, которое мы ищем, совпадает с номером на среднем элементе: мы закончили!
• Случай 2: число, которое мы ищем, меньше: мы будем искать только элементы, которые предшествуют среднему элементу.
• Случай 3: число, которое мы ищем, больше: мы будем искать только по последующим элементам.

В нашем примере число, которое мы ищем, равно 11, а средний элемент равен 5; так как 11 > 5, мы будем искать только в подсписке элементов больше 5, а именно [7, 9, 11],

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

В целом такой подход требует log(n) итераций; следовательно, алгоритм O(log(n)),

Обратите внимание, что последний работает только для отсортированных списков.