Что дешевле: отсортировать массив и затем выполнить поиск, или использовать перебор для поиска элемента?

Зависит от контекста.

1. Однократный поиск в несортированном массиве:

   • Отсортировать: Сложность сортировки обычно $O(n \log n)$ или $O(n^2)$ (зависит от алгоритма).
   • Поиск (бинарный после сортировки): $O(\log n)$.
   • Итого: $O(n \log n)$ или $O(n^2)$.
   • Перебор (линейный поиск): $O(n)$.
   • Итого: $O(n)$.
   • В данном случае перебор ($O(n)$) дешевле, чем сортировка + поиск ($O(n \log n)$ или хуже).

2. Многократный поиск в массиве:

   • Если требуется выполнить $k$ поисков в одном и том же массиве.
   • Отсортировать один раз: $O(n \log n)$ или $O(n^2)$.
   • Выполнить $k$ поисков (бинарных) после сортировки: $k \times O(\log n) = O(k \log n)$.
   • Итого: $O(n \log n + k \log n)$ или $O(n^2 + k \log n)$.
   • Выполнить $k$ переборов (линейных): $k \times O(n) = O(kn)$.
   • Итого: $O(kn)$.
   • Для больших $k$ ($k > \log n$) сортировка с последующим бинарным поиском становится дешевле: $O(n \log n + k \log n)$ vs $O(kn)$.

3. Особые случаи:

   • Если массив уже частично упорядочен или имеет специальную структуру, существуют более быстрые алгоритмы сортировки или поиска.
   • Хэш-таблицы (Set или Hash в Ruby)