Kas yra pigiau: išrikiuoti masyvą ir tada ieškoti, ar…

Priklauso nuo konteksto.

** Vienkartinis paieška nesortuotame masyve:**
- Rūšiavimas: Rūšiavimo laikas dažniausiai yra $O(n \log n)$ arba $O(n^2)$ (priklauso nuo algoritmo).
- Paieška (binarinė po rūšiavimo): $O(\log n)$.
- Iš viso: $O(n \log n)$ arba $O(n^2)$.
- Linijinis paieška: $O(n)$.
- Iš viso: $O(n)$.
- Šiuo atveju, paieška ($O(n)$) yra pigesnė nei rūšiavimas + paieška ($O(n \log n)$ arba daugiau).
** Daugkartinė paieška masyve:**
- Jei reikia atlikti $k$ paieškų tame pačiame masyve.
- Vieną kartą rūšiuoti: $O(n \log n)$ arba $O(n^2)$.
- Atlikti $k$ binarines paieškas po rūšiavimo: $k \times O(\log n) = O(k \log n)$.
- Iš viso: $O(n \log n + k \log n)$ arba $O(n^2 + k \log n)$.
- Atlikti $k$ linijines paieškas: $k \times O(n) = O(kn)$.
- Iš viso: $O(kn)$.
- Jei $k$ yra didelis ($k > \log n$), rūšiavimas su binarine paieška tampa pigesnis: $O(n \log n + k \log n)$ prieš $O(kn)$.
Ypatingi atvejai:
- Jei masyvas jau yra iš dalies surūšiuotas arba turi specialią struktūrą, yra greitesnių rūšiavimo ar paieškos algoritmų.
- Hesh lentelės (Set arba Hash Ruby kalboje) vidutiniškai užtikrina $O(1)$ paieškos laiką, kuris dažnai yra greitesnis nei bet kuris rūšiavimo ar linijinės paieškos metodas.

Išvada: Vienkartinė paieška, linijinė paieška yra pigesnė. Daugkartinė paieška tame pačiame masyve, rūšiavimas su binarine paieška tampa naudingesnis, kai paieškų skaičius yra pakankamai didelis. Jei svarbus paieškos greitis ir duomenų struktūra gali būti keičiama, naudoti Set arba Hash yra optimaliausias sprendimas.

Pavyzdys linijinės paieškos Ruby kalboje:

# Elemento paieška nesortuotame masyve
array = [5, 2, 8, 1, 9, 4]
target = 8

found = nil
array.each do |element|
  if element == target
    found = element
    break # Sustojama po pirmo atitikmens radimo
  end
end

puts found # => 8

Pavyzdys rūšiavimo ir binarinės paieškos Ruby kalboje (naudojant standartinius metodus):

# Rūšiavimas
array = [5, 2, 8, 1, 9, 4]
sorted_array = array.sort # $O(n \log n)$ Ruby Timsort algoritmas

# Binarinė paieška (Ruby turi bsearch metodą)
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 "Elementas nerastas"
end

Kas yra pigiau: išrikiuoti masyvą ir tada ieškoti, ar naudoti perėjimą elemento paieškai?