Binər axtarış

2.1 İkili axtarışın tərifi və onun əsas konsepsiyaları

İkili axtarış — bu, sıralanmış massivdə elementin axtarışı üçün istifadə olunan bir alqoritmdir və bu massivləri hissələrə bölmə ilə işləyir. Bu alqoritm böyük massivlər üçün xətkeş axtarışına nisbətən xeyli effektivdir, çünki hər iterasiyada massiv bir azaldılır.

Əsas konsepsiyalar:

• Sıralanmış massiv: İkili axtarış yalnız sıralanmış massivlərdə işləyir.
• İkiye bölmə: Alqoritm axtarılan elementi massiv ortasındakı element ilə müqayisə edir.
• Reqursiv və ya iterativ bölmə: Əgər axtarılan element ortancadan kiçikdirsə, axtarış massiv solda davam edir, əks halda isə sağda.
• Dayandırma şərti: Axtarış element tapıldıqda və ya axtarış intervalı boş qalanda dayanır.

Vacibdir! İkili axtarış üçün sıralanmış massiv lazımdır.

İkili axtarışın düzgün işləməsi üçün giriş məlumatları artan sıralanma ilə sıralanmalıdır. Bu əsas və yeganə tələbatdır, çünki alqoritm massivdəki elementlərin sıralanmış olduğunu nəzərə alır. Bunun sayəsində o, hər axtarılan addımda elementlərin yarısını çıxara bilir.

Sıralanmış massiv nümunəsi:

sorted_array = [1, 3, 5, 7, 9, 11, 13]

2.2 İkili axtarışın addım-addım həyata keçirilməsi

İkili axtarışın iş prinsipi:

1. İlkinləşdirmə: Axtarışın başlanğıc sərhədlərini təyin edin (massivin sol və sağ sərhədləri).
2. Orta elementi seçin: Massivin orta elementinin indeksini tapın.
3. Müqayisə: Orta elementi axtarılan dəyər ilə müqayisə edin.
4. Sərhədləri yeniləyin:
   1. Əgər orta element axtarılan dəyərə bərabərdirsə, onun indeksini qaytarın.
   2. Əgər axtarılan dəyər orta elementdən kiçiksə, sağ sərhədi yeniləyin.
   3. Əgər böyükdürsə — sol sərhədi yeniləyin.
5. Təkrar: Element tapılana qədər və ya sol sərhəd sağ sərhəddən böyük olmayana qədər 2-4 addımları təkrarlayın.

Addım-addım alqoritm:

1. İlkinləşdirmə: left 0-a və right len(arr) - 1-ə təyin edin.
2. Orta elementi hesablayın: mid = (left + right) // 2
3. Hədəf element ilə müqayisə edin:
   1. Əgər arr[mid] == target, mid-i qaytarın
   2. Əgər arr[mid] < target, left = mid + 1-i yeniləyin
   3. Əgər arr[mid] > target, right = mid - 1-i yeniləyin
4. Təkrar edin: left <= right-ə qədər 2-ci addıma dönün
5. Əgər element tapılmadısa: -1 qaytarın

İkili axtarışın iterativ həyata keçirilməsi Python-da:

def binary_search(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

# İstifadə nümunəsi:
sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
result = binary_search(sorted_array, target)
print(f"Element {target} indeksdə tapıldı {result}")  # Çıxış: Element 7 indeksdə tapıldı 3

2.3 Binary axtarışın zaman mürəkkəbliyi O(log n)

Binary axtarışın zaman mürəkkəbliyi O(log n) təşkil edir, burada n massivdəki elementlərin sayını göstərir. Bu o deməkdir ki, alqoritm hər addımda elementlərin sayını ikiyə bölür, bu da lineer axtarışın O(n) mürəkkəbliyindən daha sürətli edir.

Zaman mürəkkəbliyinin analiz edilməsi:

• Ən yaxşı hal (Best case): Element ilk addımda tapılır, O(1).
• Orta hal (Average case): O(log n).
• Ən pis hal (Worst case): Element son addımda tapılır və ya yoxdur, O(log n).

Zaman mürəkkəbliyinin analizi üçün nümunə:

sorted_array = [1, 3, 5, 7, 9, 11, 13]
target = 7
index = binary_search(sorted_array, target)
print(f"Element {target} indekste tapıldı {index}")  # Çıxış: Element 7 indekste tapıldı 3

# Alqoritm elementi tapmaq üçün 3 addım atıb (7 elementdən logaritm), 
# bu da O(log n)-ə uyğundur

Mürəkkəbliyinin qrafik təmsili:

16 elementdən ibarət bir massiv təsəvvür edin.

Tutaq ki, biz 15 elementini axtarırıq, onda addımlar belə olacaq:

Birinci addım. Orta elementi yoxlayır (8 element qalır).

İkinci addım. Qalan yarıda orta elementi yoxlayır (4 element qalır).

Üçüncü addım. Qalan yarıda orta elementi yoxlayır (2 element qalır).

Dördüncü addım. Son elementi yoxlayır (1 element qalır).

Nəticədə alqoritm 16 elementdən ibarət massiv üçün 4 addım atacaq, bu da 2 əsasında 16-nın logaritminə bərabərdir, yəni log2(16) = 4. Bu da logaritmik mürəkkəblik olan O(log n) deməkdir.