Ce este mai ieftin: să sortezi un array și apoi să…

Depinde de context.

Căutare unică într-un array nesortat:
- Sortare: Complexitatea sortării este de obicei $O(n \log n)$ sau $O(n^2)$ (depinde de algoritm).
- Căutare (binară după sortare): $O(\log n)$.
- În total: $O(n \log n)$ sau $O(n^2)$.
- Parcurgere liniară (căutare liniară): $O(n)$.
- În total: $O(n)$.
- În acest caz, parcurgerea ($O(n)$) este mai ieftină decât sortarea + căutarea ($O(n \log n)$ sau mai mult).
Căutări multiple într-un array:
- Dacă trebuie să efectuați $k$ căutări în același array.
- Sortați o dată: $O(n \log n)$ sau $O(n^2)$.
- Efectuați $k$ căutări binare după sortare: $k \times O(\log n) = O(k \log n)$.
- În total: $O(n \log n + k \log n)$ sau $O(n^2 + k \log n)$.
- Efectuați $k$ parcurgeri liniare: $k \times O(n) = O(kn)$.
- În total: $O(kn)$.
- Pentru valori mari ale lui $k$ ($k > \log n$), sortarea cu căutare binară devine mai ieftină: $O(n \log n + k \log n)$ față de $O(kn)$.
Cazuri speciale:
- Dacă array-ul este deja parțial sortat sau are o structură specială, există algoritmi de sortare sau căutare mai rapidi.
- Tabelele hash (Set sau Hash în Ruby) oferă în medie $O(1)$ timp pentru căutare, ceea ce de obicei este mai rapid decât orice metodă bazată pe sortare sau căutare liniară.

Concluzie: Pentru o singură căutare, parcurgerea este mai ieftină. Pentru multiple căutări în același array, sortarea cu căutare binară devine mai eficientă pentru un număr suficient de mare de căutări. Dacă viteza de căutare este critică și structura de date poate fi modificată, utilizarea Set sau Hash poate fi cea mai optimă soluție.

Exemplu de căutare liniară în Ruby:

# Căutarea unui element într-un array nesortat
array = [5, 2, 8, 1, 9, 4]
target = 8

found = nil
array.each do |element|
  if element == target
    found = element
    break # Oprirea după găsirea primei potriviri
  end
end

puts found # => 8

Exemplu de sortare și căutare binară în Ruby (folosind metodele standard):

# Sortare
array = [5, 2, 8, 1, 9, 4]
sorted_array = array.sort # O(n \log n) pentru Timsort în Ruby

# Căutare binară (Ruby are 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 "Elementul nu a fost găsit"
end

Ce este mai ieftin: să sortezi un array și apoi să cauți, sau să folosești o parcurgere pentru a găsi un element?