Бинарный поиск и последовательный поиск

Question

При каком размере массива лучше использовать последовательный поиск поверх бинарного поиска (необходимо сначала отсортировать) для этих конкретных ситуаций.Первый случай, когда все значения массива являются случайными числами и не отсортированы.Второй случай - когда значения или случайные числа массива сортируются численно от наименьшего к наибольшему или от наибольшего к наименьшему.Предполагается, что при поиске вы пытаетесь найти только одно число в массиве.

Случай 1: Случайные числа

Случай 2: Уже отсортировано

Answer 1

Алгоритм последовательного поиска имеет наихудшее время выполнения O (n) и не зависит от того, отсортированы ли данные или нет.

Алгоритм бинарного поиска имеет наихудшее время выполнения O (logn), однако для использования алгоритма данные должны быть отсортированы.Если данные не отсортированы, сортировка данных займет O (nlogn) время.

Следовательно:

Случай 1: Если данные не отсортированы, последовательный поиск будет более эффективным, так как это займет O (n) времени.Бинарный поиск потребует, чтобы данные были отсортированы по O (nlogn), а затем произведен поиск по O (logn).Следовательно, временная сложность будет O (nlogn) + O (logn) = O (nlogn).

Случай 2: при сортировке данных бинарный поиск будет более эффективным по времени, так как он займет толькоO (logn) время, в то время как последовательный поиск все равно займет O (n) время.

Answer 2

Бинарный поиск всегда лучше.Но двоичный поиск всегда требует, чтобы массив был отсортирован.