Čo je lacnejšie: zoradiť pole a potom hľadať, alebo…

Závisí od kontextu.

Jednorazové vyhľadávanie v nezořadenom poli:
- Zoradiť: Časová zložitosť zoradenia je zvyčajne $O(n \log n)$ alebo $O(n^2)$ (závisí od algoritmu).
- Vyhľadávanie (binárne po zoradení): $O(\log n)$.
- Celkovo: $O(n \log n)$ alebo $O(n^2)$.
- Prehľadávanie (lineárne vyhľadávanie): $O(n)$.
- Celkovo: $O(n)$.
- V tomto prípade je prehľadávanie ($O(n)$) lacnejšie ako zoradenie + vyhľadávanie ($O(n \log n)$ alebo viac).
Viackrát vyhľadávanie v poli:
- Ak je potrebné vykonať $k$ vyhľadávaní v rovnakom poli.
- Raz zoradiť: $O(n \log n)$ alebo $O(n^2)$.
- Vykonať $k$ binárnych vyhľadávaní po zoradení: $k \times O(\log n) = O(k \log n)$.
- Celkovo: $O(n \log n + k \log n)$ alebo $O(n^2 + k \log n)$.
- Vykonať $k$ lineárnych vyhľadávaní: $k \times O(n) = O(kn)$.
- Celkovo: $O(kn)$.
- Pre veľké $k$ ($k > \log n$) sa zoradenie s následným binárnym vyhľadávaním stáva lacnejším: $O(n \log n + k \log n)$ verzus $O(kn)$.
Špeciálne prípady:
- Ak je pole už čiastočne zoradené alebo má špeciálnu štruktúru, existujú rýchlejšie algoritmy zoradenia alebo vyhľadávania.
- Hash tabuľky (Set alebo Hash v Ruby) poskytujú priemerný čas $O(1)$ na vyhľadávanie, čo je zvyčajne rýchlejšie ako akákoľvek metóda založená na zoradení alebo lineárnom vyhľadávaní.

Záver: Pre jednoduché vyhľadávanie je lacnejšie prehľadávanie. Pre viackrát vyhľadávanie v tom istom poli sa zoradenie s binárnym vyhľadávaním stáva výhodnejším pri dostatočne veľkom počte vyhľadávaní. Ak je rýchlosť vyhľadávania dôležitá a štruktúra dát môže byť zmenená, použitie Set alebo Hash môže byť najoptimálnejším riešením.

Príklad lineárneho vyhľadávania v Ruby:

# Vyhľadávanie prvku v nezořadenom poli
array = [5, 2, 8, 1, 9, 4]
target = 8

found = nil
array.each do |element|
  if element == target
    found = element
    break # Zastavenie po nájdení prvého zhody
  end
end

puts found # => 8

Príklad zoradenia a binárneho vyhľadávania v Ruby (s použitím štandardných metód):

# Zoradenie
array = [5, 2, 8, 1, 9, 4]
sorted_array = array.sort # $O(n \log n)$ pre Timsort v Ruby

# Binárne vyhľadávanie (Ruby má vstavaný 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 "Prvok nie je nájdený"
end

Čo je lacnejšie: zoradiť pole a potom hľadať, alebo použiť prehľadávanie na nájdenie prvku?