Rekursiv binar axtarış

3.1 Rekursiv binar axtarışın iş prinsipi

Binar axtarış — sıralanmış massivdə element tapmaq üçün nəzərdə tutulmuş bir alqoritmdir. Bu alqoritm "böl və idarə et" prinsipinə əsaslanır. İstənilən elementi massivdəki orta elementlə müqayisə edir və axtarışın hansı hissəsində davam edəcəyinə qərar verir. Rekursiv binar axtarış bu prosesi, massiv sərhədlərini yeniləyərək özünü çağırmaqla təkrarlayır.

Alqoritmin addımları:

1. İstənilən elementi massivdəki orta elementlə müqayisə edirik.
2. Əgər orta element istənilən elementlə uyğun gəlirsə, onun indeksini qaytarırıq.
3. Əgər istənilən element kiçikdirsə, axtarışı massivinin sol yarısında təkrarlayırıq.
4. Əgər istənilən element böyükdürsə, axtarışı massivinin sağ yarısında təkrarlayırıq.
5. Element tapılana və ya massiv tükənənə qədər prosesi təkrarlayırıq.

Rekursiv binar axtarışın həyata keçirilməsi

Python-da nümunə:

def binary_search_recursive(arr, target, left, right):
    if left > right:
        return -1  # Əsas hal: element tapılmadı
            
    mid = (left + right) // 2  # Massivin ortasını tapırıq
            
    if arr[mid] == target:
        return mid  # Əsas hal: element tapıldı
    elif arr[mid] < target:
        return binary_search_recursive(arr, target, mid + 1, right)  # Sağ yarıya baxırıq
    else:
        return binary_search_recursive(arr, target, left, mid - 1)  # Sol yarıya baxırıq
        
# İstifadə nümunəsi:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 7
result = binary_search_recursive(arr, target, 0, len(arr) - 1)
print(f"Element bu mövqedə tapıldı: {result}")  # Çıxarış: Element bu mövqedə tapıldı: 6
        

3.2 İterativ ikili axtarış ilə müqayisə

İterativ ikili axtarış:

def binary_search_iterative(arr, target):
    left, right = 0, len(arr) - 1
            
    while left <= right:
        mid = (left + right) // 2
                
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
            
    return -1  # Element tapılmadı
        
# İstifadə nümunəsi:
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
target = 7
result = binary_search_iterative(arr, target)
print(f"Element mövqeyi: {result}")  # Çap edəcək: Element mövqeyi: 6
        

Müqayisə:

Reallaşdırma sadəliyi:

• Rekursiv alqoritm adətən daha sadə və qısa olur, amma rekursiv çağırışları anlamağı tələb edir.
• İterativ alqoritm dövrdən istifadə edir və bu, yeni başlayan proqramçılar üçün daha asan ola bilər.

Yaddaş:

• Rekursiv alqoritm çağırış yığından istifadə edir, bu isə böyük massivlərdə yaddaş istifadəsinin artmasına səbəb ola bilər.
• İterativ alqoritm sabit yaddaş miqdarı istifadə edir, bu da onu yaddaş istifadəsi baxımından daha səmərəli edir.

İcra performansı:

• Hər iki alqoritmin vaxt kompleksi O(log n) səviyyəsindədir.
• Rekursiv alqoritm rekursiv çağırışların əlavə resurslarına görə, xüsusən rekursiya dərinliyi çox olduqda daha yavaş ola bilər.

3.3 Rekursiv Binary Search üçün misal tapşırıqlar

Rekursiv binary search — bu, çeşidlənmiş massivlərdə elementləri tez tapmağa kömək edən güclü bir alqoritmdir. O, "böl və hökm sür" prinsipinə əsaslanır və tapşırığı kiçik alt tapşırıqlara bölmək üçün rekursiyadan istifadə edir.

Rekursiv və iterativ yanaşmaların müqayisəsi göstərir ki, onların hər birinin konkret tapşırıqdan asılı olaraq üstünlükləri və çatışmazlıqları var. Bu alqoritmləri və onların tətbiqini anlamaq proqramlaşdırmada axtarış tapşırıqlarını səmərəli həll etməyə imkan verir.

Məsələn, aşağıdakılar:

Çeşidlənmiş massivdə elementin axtarışı:

Məsələn, imtahan nəticələrini qiymətləndirmək, çeşidlənmiş açarlara görə məlumat bazasında axtarış və s. üçün massivdə müəyyən bir elementi axtarmaq.

Elementin mövcudluğunun yoxlanılması:

Məsələn, icazə verilmiş istifadəçilər, identifikator siyahısında müəyyən bir dəyərin mövcudluğunu yoxlamaq və s.

Ən yaxın dəyərin axtarışı:

Məsələn, ən yaxın mağazanın, stansiyanın və s. axtarışı zamanı verilmiş dəyərə ən yaxın olan elementi tapmaq.

Optimizasiya:

Çeşidlənmiş massivdə optimal dəyəri tapmağı tələb edən məsələlərin həlli, məsələn, funksiyalarda minimum və ya maksimum nöqtəni tapmaq.