Co je levnější: setřídit pole a pak hledat, nebo…

Záleží na kontextu.

Jednotlivé hledání v nenavřazeném poli:
- Seřadit: Složitost řazení je obvykle $O(n \log n)$ nebo $O(n^2)$ (závisí na algoritmu).
- Hledání (binární po seřazení): $O(\log n)$.
- Celkem: $O(n \log n)$ nebo $O(n^2)$.
- Lineární průchod (sekvenční hledání): $O(n)$.
- Celkem: $O(n)$.
- V tomto případě je průchod ($O(n)$) levnější než řazení + hledání ($O(n \log n)$ nebo horší).
Vícenásobné hledání ve stejném poli:
- Pokud je třeba provést $k$ hledání ve stejném poli.
- Jednou seřadit: $O(n \log n)$ nebo $O(n^2)$.
- Provést $k$ binárních hledání po seřazení: $k \times O(\log n) = O(k \log n)$.
- Celkem: $O(n \log n + k \log n)$ nebo $O(n^2 + k \log n)$.
- Provést $k$ lineárních průchodů: $k \times O(n) = O(kn)$.
- Celkem: $O(kn)$.
- Pro velká $k$ ($k > \log n$) je levnější řazení s binárním hledáním: $O(n \log n + k \log n)$ vs. $O(kn)$.
Zvláštní případy:
- Pokud je pole již částečně seřazené nebo má speciální strukturu, existují rychlejší algoritmy řazení nebo hledání.
- Hash tabulky (Set nebo Hash v Ruby) nabízejí průměrně $O(1)$ čas pro hledání, což je obvykle rychlejší než jakákoli metoda založená na řazení nebo lineárním hledání.

Závěr: Pro jedno hledání je levnější průchod. Pro vícenásobná hledání ve stejném poli je efektivnější řazení s binárním hledáním, pokud je počet hledání dostatečně velký. Pokud je rychlost hledání kritická a datová struktura může být změněna, použití Set nebo Hash je nejoptimálnější řešení.

Příklad lineárního hledání v Ruby:

# Hledání prvku v nenavřazeném poli
array = [5, 2, 8, 1, 9, 4]
target = 8

found = nil
array.each do |element|
  if element == target
    found = element
    break # Ukončit po nalezení prvního shody
  end
end

puts found # => 8

Příklad řazení a binárního hledání v Ruby (s použitím standardních metod):

# Řazení
array = [5, 2, 8, 1, 9, 4]
sorted_array = array.sort # O(n \log n) v Ruby s Timsort

# Binární hledání (Ruby má 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 "Prvek nebyl nalezen"
end

Co je levnější: setřídit pole a pak hledat, nebo použít průchod k nalezení prvku?