Axtarış alqoritmləri

Murad 1-dən 100-ə qədər bir ədəd tutur, Aysel isə onu tapmalıdır. Hər təxmindən sonra Murad yalnız «daha böyükdür», «daha kiçikdir» və ya «tapdın» deyir. Aysel 1, 2, 3… deyə ardıcıl soruşsa, 100 cəhd lazım ola bilər. Amma o, 50-dən başlayıb hər dəfə aralığı yarıya bölsə, ədədi ən çoxu 7 cəhddə tapacaq. Bu iki yanaşma iki məşhur alqoritmdir: xətti və ikili axtarış.

Xətti axtarış

Xətti (ardıcıl) axtarışda siyahının elementləri birincidən başlayaraq bir-bir axtarılan qiymətlə müqayisə olunur. Uyğun element tapılanda axtarış dayanır; siyahının sonuna çatıb tapmasaq, deməli, belə element yoxdur.

Xətti axtarışın üstünlüyü sadəliyidir: o, istənilən siyahıda, hətta nizamlanmamış siyahıda da işləyir. Çatışmazlığı isə yavaşlığıdır: n elementli siyahıda ən pis halda n müqayisə lazımdır.

def linear_search(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i
    return -1

numbers = [7, 3, 23, 9, 15]
print(linear_search(numbers, 23))
print(linear_search(numbers, 4))

2
-1

İkili axtarış

İkili axtarış yalnız nizamlanmış (məsələn, artan sıra ilə düzülmüş) siyahıda işləyir, amma çox sürətlidir. Hər addımda axtarılan qiymət aralığın ortasındakı elementlə müqayisə edilir və siyahının yarısı birdən kənara atılır.

1. 1
   Ortanı tap

   Axtarış aralığının ortasındakı elementi götür.

2. 2
   Müqayisə et

   Orta element axtarılan qiymətə bərabərdirsə, element tapıldı — axtarış bitdi.

3. 3
   Yarını at

   Axtarılan qiymət orta elementdən kiçikdirsə, axtarışı sol yarıda, böyükdürsə, sağ yarıda davam etdir.

4. 4
   Təkrar et

   Element tapılana və ya aralıq boş qalana qədər 1–3-cü addımları təkrarla. Aralıq boşdursa, element siyahıda yoxdur.

def binary_search(items, target):
    low, high = 0, len(items) - 1
    steps = 0
    while low <= high:
        mid = (low + high) // 2
        steps += 1
        if items[mid] == target:
            return mid, steps
        elif items[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1, steps

numbers = [3, 8, 12, 17, 23, 31, 37, 42, 50]
print(binary_search(numbers, 37))
print(binary_search(numbers, 5))

(6, 2)
(-1, 3)

Hansı daha sürətlidir?

İkili axtarışda hər müqayisə siyahını iki dəfə kiçildir, ona görə siyahı 2 dəfə böyüyəndə cəmi bir müqayisə əlavə olunur. Böyük siyahılarda fərq heyrətamiz olur: