Mis on odavam: massiivi sorteerida ja siis otsida…

Konkreets kontekstist sõltub.

** Ühekordne otsing mitte-sorted massiivis:**
- Sorteerimine: Sorteerimise aeg on tavaliselt $O(n \log n)$ või $O(n^2)$ (sõltuvalt algoritmist).
- Otsing (binaarne pärast sorteerimist): $O(\log n)$.
- Kokku: $O(n \log n)$ või $O(n^2)$.
- Lineaarne otsing: $O(n)$.
- Kokku: $O(n)$.
- Antud juhul on otsing ($O(n)$) odavam kui sorteerimine + otsing ($O(n \log n)$ või rohkem).
** Mitmekordne otsing massiivis:**
- Kui on vaja teha $k$ otsingut samas massiivis.
- Ühekordne sorteerimine: $O(n \log n)$ või $O(n^2)$.
- Teha $k$ binaarset otsingut pärast sorteerimist: $k \times O(\log n) = O(k \log n)$.
- Kokku: $O(n \log n + k \log n)$ või $O(n^2 + k \log n)$.
- Teha $k$ lineaarset otsingut: $k \times O(n) = O(kn)$.
- Kokku: $O(kn)$.
- Kui $k$ on suur ($k > \log n$), siis sorteerimine koos binaarse otsinguga muutub odavamaks: $O(n \log n + k \log n)$ versus $O(kn)$.
Spetsiaalsed juhtumid:
- Kui massiiv on juba osaliselt sorteeritud või omab erilist struktuuri, on olemas kiiremad sorteerimis- või otsingualgoritmid.
- Hash-tabelid (Set või Hash Ruby-s) tagavad keskmiselt $O(1)$ otsinguaega, mis on tavaliselt kiirem kui mis tahes sorteerimise või lineaarse otsingu meetod.

Järeldus: Ühekordne otsing, lineaarne otsing on odavam. Mitmekordne otsing samas massiivis, sorteerimine koos binaarse otsinguga muutub kasulikumaks, kui otsingute arv on piisavalt suur. Kui otsingu kiirus on oluline ja andmestruktuur võib muutuda, on Set või Hash kõige optimaalsem lahendus.

Näide lineaarse otsingu Ruby-s:

# Elementi otsimine mitte-sorted massiivis
array = [5, 2, 8, 1, 9, 4]
target = 8

found = nil
array.each do |element|
  if element == target
    found = element
    break # Peatub pärast esimese sobivuse leidmist
  end
end

puts found # => 8

Näide sorteerimisest ja binaarsest otsingust Ruby-s (kasutades standardmeetodeid):

# Sorteerimine
array = [5, 2, 8, 1, 9, 4]
sorted_array = array.sort # $O(n \log n)$ Ruby Timsort-i jaoks

# Binaarne otsing (Ruby-l on 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 "Elementi ei leitud"
end

Mis on odavam: massiivi sorteerida ja siis otsida, või kasutada läbimise meetodit elemendi leidmiseks?