Для одного поиска в неупорядоченном массиве линейный перебор занимает O(n), а сортировка сравнением и бинарный поиск — обычно O(n log n). Для k поисков сравнивают O(kn) с O(n log n + k log n). Точный порог зависит от данных и реализации; для проверки наличия альтернативой служат Set/Hash с дополнительной памятью.
Что дешевле: сортировка с бинарным поиском или линейный перебор?
Для одного поиска подготовка обычно не окупается. Для серии запросов сравнивают общую стоимость сортировки, поисков и поддержки структуры.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Для одного поиска в неупорядоченном массиве обычно выгоднее перебор. Его худшая временная сложность — O(n) при постоянной стоимости сравнения. Если сначала применить сортировку сравнением со стоимостью O(n log n), а затем бинарный поиск O(log n), подготовка определит общую стоимость.
Для k поисков в неизменном наборе ситуация другая:
| Способ | Суммарная стоимость |
|---|---|
| Линейный поиск каждый раз | O(kn) |
| Одна сортировка и бинарные поиски | O(n log n + k log n) |
Подготовка может окупиться на серии запросов. Но правило «достаточно ровно k > log n» не является универсальным порогом времени: имеют значение константы, стоимость сравнения, расположение совпадений и размер массива. Если данные часто меняются, нужно учитывать поддержку порядка.
Пример для массива целых чисел в Ruby:
values = [5, 2, 8, 1, 9, 4]
target = 8
p values.include?(target) # true
sorted = values.sort
index = sorted.bsearch_index { |value| value >= target }
p(!index.nil? && sorted[index] == target) # true
Предикат бинарного поиска должен быть монотонным. Здесь поиск возвращает первое значение не меньше цели, поэтому нужна отдельная проверка равенства: для отсутствующего 7 найденным кандидатом будет 8. Array#bsearch_index
Если требуется только многократно проверять наличие значения, можно построить Set или Hash: это дополнительная память и время построения, зато поиск обычно имеет среднюю стоимость O(1) при обычных предположениях о хешировании. Бинарный поиск полезен также для границ диапазонов. Выбор определяется всей нагрузкой, а не стоимостью одного шага.