İkili axtarış alqoritmi necə işləyir?

İkili axtarış, sıralanmış bir massivə baxaraq və axtarış intervalını ardıcıl olaraq yarıya bölərək işləyir.

1. Başlanğıc: Axtarış intervalının sol və sağ sərhədləri müəyyən edilir (adətən massivlərin başlanğıcı və sonu).
2. Müqayisə: Intervalın ortasının indeksi hesablanır. Bu indeksdəki dəyər axtarılan elementlə müqayisə edilir.
3. İntervalın azaldılması:
   • Əgər ortadakı dəyər axtarılan ilə uyğun gəlirsə, element tapılıb.
   • Əgər ortadakı dəyər axtarılandan böyükdürsə, axtarış intervalın sol yarısında davam edir. Sağ sərhəd ortadan - 1-ə köçürülür.
   • Əgər ortadakı dəyər axtarılandan kiçikdirsə, axtarış intervalın sağ yarısında davam edir. Sol sərhəd ortadan + 1-ə köçürülür.
4. Təkrarlama: 2 və 3-cü addımlar element tapılana və ya axtarış intervalı boşalana qədər təkrarlanır.

Algoritmin mürəkkəbliyi O(log n)-dir, bu isə böyük massivlər üçün xətti axtarışdan çox daha səmərəlidir.

Python-da nümunə tətbiqi:

def binary_search(arr, target):
    """
    İkili axtarışın tətbiqi.
    Sıralanmış massiv və axtarılan dəyəri qəbul edir.
    Elementin indeksini və ya tapılmayıbsa -1 qaytarır.
    """
    sol, sağ = 0, len(arr) - 1

    while sol <= sağ:
        orta = (sol + sağ) // 2  # Orta indeksin hesablanması
        orta_dəyər = arr[orta]      # Orta dəyərin alınması

        if orta_dəyər == target:
            return orta  # Element tapıldı
        elif orta_dəyər < target:
            sol = orta + 1  # Sağda axtarış
        else: # orta_dəyər > target
            sağ = orta - 1 # Solda axtarış

    return -1 # Element tapılmadı