Кое е по-евтино: да сортирате масив и след това да…

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

Единично търсене в несортиран масив:
- Сортиране: Сложността на сортирането е обикновено $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)$ или повече).
Многократно търсене в един масив:
- Ако трябва да извършите $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)$ срещу $O(kn)$.
Специални случаи:
- Ако масивът вече е частично сортиран или има специална структура, съществуват по-бързи алгоритми за сортиране или търсене.
- Хеш таблиците (Set или Hash в Ruby) предлагат средно $O(1)$ време за търсене, което обикновено е по-бързо от всякакъв метод, базиран на сортиране или линейно търсене.

Заключение: За единично търсене, прегледът е по-евтин. За многократно търсене в същия масив, сортирането с бинарно търсене става по-ефективно при достатъчно голям брой търсения. Ако скоростта на търсене е критична и структурата на данните може да бъде променена, използването на Set или Hash може да бъде най-оптималното решение.

Пример за линейно търсене в Ruby:

# Търсене на елемент в несортиран масив
array = [5, 2, 8, 1, 9, 4]
target = 8

found = nil
array.each do |element|
  if element == target
    found = element
    break # Спира след намиране на първото съвпадение
  end
end

puts found # => 8

Пример за сортиране и бинарно търсене в Ruby (с използване на стандартни методи):

# Сортиране
array = [5, 2, 8, 1, 9, 4]
sorted_array = array.sort # O(n \log n) за Timsort в Ruby

# Бинарно търсене (Ruby има bsearch)
target = 8
index = sorted_array.bsearch_index { |x| x >= target } # O(\log n)

if index && sorted_array[index] == target
  puts sorted_array[index] # => 8
else
  puts "Елемент не е намерен"
end

Кое е по-евтино: да сортирате масив и след това да търсите, или да използвате обхождане за намиране на елемент?