Kas ir lētāk: sakārtot masīvu un pēc tam meklēt, vai izmantot pārbaudi, lai atrastu elementu?

Atkarīgs no konteksta.

1. ** Vienreizēja meklēšana nesortētā masīvā:**

   • Kārtošana: Kārtošanas laiks parasti ir $O(n \log n)$ vai $O(n^2)$ (atkarīgs no algoritma).
   • Meklēšana (binārā pēc kārtošanas): $O(\log n)$.
   • Kopā: $O(n \log n)$ vai $O(n^2)$.
   • Lineāra meklēšana: $O(n)$.
   • Kopā: $O(n)$.
   • Šajā gadījumā, meklēšana ($O(n)$) ir lētāka nekā kārtošana + meklēšana ($O(n \log n)$ vai vairāk).

2. ** Daudzkārtēja meklēšana masīvā:**

   • Ja nepieciešams veikt $k$ meklējumus tajā pašā masīvā.
   • Vienu reizi kārtošana: $O(n \log n)$ vai $O(n^2)$.
   • Veikt $k$ bināros meklējumus pēc kārtošanas: $k \times O(\log n) = O(k \log n)$.
   • Kopā: $O(n \log n + k \log n)$ vai $O(n^2 + k \log n)$.
   • Veikt $k$ lineārus meklējumus: $k \times O(n) = O(kn)$.
   • Kopā: $O(kn)$.
   • Ja $k$ ir liels ($k > \log n$), kārtošana ar bināro meklēšanu kļūst izdevīgāka: $O(n \log n + k \log n)$ pret $O(kn)$.

3. Īpaši gadījumi:

   • Ja masīvs jau ir daļēji sakārtots vai tam ir īpaša struktūra, ir ātrāki kārtošanas vai meklēšanas algoritmi.
   • Hesh tabulas (Set vai Hash Ruby) vidēji nodrošina $O(1)$ laiku meklēšanai, kas parasti ir ātrāk nekā jebkurš kārtošanas vai lineāras meklēšanas metode.

Secinājums: Vienreizēja meklēšana, lineāra meklēšana ir lētāka. Daudzkārtēja meklēšana tajā pašā masīvā, kārtošana ar bināro meklēšanu kļūst izdevīgāka, kad meklējumu skaits ir pietiekami liels. Ja meklēšanas ātrums ir svarīgs un datu struktūra var tikt mainīta, tad Set vai Hash ir optimālākais risinājums.

Lineāras meklēšanas piemērs Ruby:

# Elementa meklēšana nesortētā masīvā
array = [5, 2, 8, 1, 9, 4]
target = 8

found = nil
array.each do |element|
  if element == target
    found = element
    break # Pārtrauc pēc pirmās atbilstības
  end
end

puts found # => 8

Kārtošanas un binārās meklēšanas piemērs Ruby (izmantojot standarta metodes):

# Kārtošana
array = [5, 2, 8, 1, 9, 4]
sorted_array = array.sort # $O(n \log n)$ Ruby Timsort algoritmā

# Binārā meklēšana (Ruby ir iebūvēts 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 "Elements nav atrasts"
end