Почему я предпочел бы бинарный поиск линейному поиску в несортированном массиве?

Question

Я прошел курс DSA на Coursera, и на этой неделе я познакомился с алгоритмами поиска. Хотя сложность бинарного поиска (O (logn)) лучше, чем линейный поиск (O (n)). Но зачем мне использовать его в несортированном массиве, учитывая тот факт, что сначала потребуется nlogn для сортировки массива.

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

Answer 1

я бы использовал его в несортированном массиве, учитывая тот факт, что сначала потребуется O ( n log n ) для сортировки массива.

Обычно один выполняет несколько запросов к одной и той же структуре данных. Действительно, посмотрите, например, на базу данных. Имеет смысл, что чаще выбирают запись с заданным первичным ключом, чем добавляют записи. Это имеет смысл, поскольку, если количество запросов было меньше количества вставок, то мы делали вставки данных, которые никогда не извлекаются, и поэтому они «бесполезны».

Кроме того, сортировка списка элементов, или построение двоичного дерева элементов действительно занимает O (n log n) . Но обновляет двоичное дерево поиска, как, например, дерево AVL [wiki] занимает O (log n) . Так что, если вы немного измените коллекцию элементов, добавив один элемент, удалив один элемент, обновив один элемент, et c. Для изменения структуры данных требуется O (log n) , и вы продолжаете поддерживать поиск O (log n) .

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

Answer 2

Ответ Виллема Ван Онсема хорошо описывает случай, когда множество запросов будет выполнено для одного и того же массива, поэтому стоит сначала потратить O (n log n) для сортировки массива. Мой ответ не имеет прямого отношения к «несортированным массивам», но существует распространенное заблуждение, что массивы либо являются несортированными, либо были отсортированы , и я думаю, что стоит обратить внимание на это неправильное представление в на случай, если это поможет читателям.

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

---

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

Поэтому, когда мы говорим бинарный поиск может использоваться только в «отсортированном массиве», это не означает, что для «сортировки» массива потребовалось O (n log n) времени. Множество данных, естественно, в порядке, без необходимости выполнять какую-либо работу по их сортировке. Несколько примеров:

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

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