Nə daha ucuzdur: massivı sıralamaq və sonra axtarış…

Kontextdən asılıdır.

Tək axtarış qeyri-sıralanmış massivdə:
- Sıralama: Sıralamanın mürəkkəbliyi adətən $O(n \log n)$ və ya $O(n^2)$-dir (alqoritmdən asılıdır).
- Axtarış (sıralamadan sonra ikili axtarış): $O(\log n)$.
- Ümumilikdə: $O(n \log n)$ və ya $O(n^2)$.
- Xəttən axtarış (gəzinti): $O(n)$.
- Ümumilikdə: $O(n)$.
- Bu halda, gəzinti ($O(n)$) sıralama + axtarışdan ($O(n \log n)$ və ya daha çox) ucuzdur.
Çoxsaylı axtarışlar eyni massivdə:
- Əgər $k$ sayda axtarış etmək lazımdırsa.
- Bir dəfə sıralayın: $O(n \log n)$ və ya $O(n^2)$.
- Sıralamadan sonra $k$ ikili axtarış aparın: $k \times O(\log n) = O(k \log n)$.
- Ümumilikdə: $O(n \log n + k \log n)$ və ya $O(n^2 + k \log n)$.
- $k$ sayda xətti gəzinti aparın: $k \times O(n) = O(kn)$.
- Ümumilikdə: $O(kn)$.
- Böyük $k$ üçün ($k > \log n$), sıralama və ikili axtarış daha ucuz olur: $O(n \log n + k \log n)$ əvəzinə $O(kn)$.
Xüsusi hallar:
- Əgər massiv artıq qismən sıralanıbsa və ya xüsusi strukturda isə, daha sürətli sıralama və ya axtarış alqoritmləri mövcuddur.
- Hash cədvəlləri (Set və ya Hash Ruby-də) orta hesabla $O(1)$ vaxtda axtarış təklif edir və adətən sıralama və ya xətti axtarışdan daha sürətlidir.

Nəticə: Tək axtarış üçün gəzinti daha ucuzdur. Eyni massivdə çoxsaylı axtarışlar üçün, sıralama və ikili axtarış kifayət qədər çox axtarış üçün daha səmərəlidir. Axtarış sürəti vacibdirsə və məlumat strukturu dəyişdirilə bilərsə, Set və ya Hash istifadə etmək ən optimal həll ola bilər.

Ruby-də xətti axtarış nümunəsi:

# Sıralanmamış massivdə element axtarışı
array = [5, 2, 8, 1, 9, 4]
target = 8

found = nil
array.each do |element|
  if element == target
    found = element
    break # Birinci uyğunluğu tapdıqdan sonra dayandır
  end
end

puts found # => 8

Ruby-də sıralama və ikili axtarış nümunəsi (standart metodlardan istifadə etməklə):

# Sıralama
array = [5, 2, 8, 1, 9, 4]
sorted_array = array.sort # O(n \log n) Ruby-də Timsort

# İkili axtarış (Ruby-də 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 "Element tapılmadı"
end

Nə daha ucuzdur: massivı sıralamaq və sonra axtarış etmək, yoxsa element tapmaq üçün keçid istifadə etmək?