DSA ikkilik qidiruv

Ikkilik qidiruv

Ikkilik qidiruv (Binary Search) algoritmi massiv bo‘ylab qidiradi va izlanayotgan qiymatning indeksini qaytaradi.

Ikkilik qidiruv algoritmi qanday ishlashini ko‘rish uchun simulyatsiyani ishga tushiring.

Qiymat topilmaganda nima sodir bo‘lishini ko‘rish uchun 5 qiymatini topishga urinib ko‘ring.

Ikkilik qidiruv chiziqli qidiruvdan ancha tez, ammo ishlashi uchun saralangan massiv talab qiladi.

Ikkilik qidiruv algoritmi massiv markazidagi qiymatni tekshirish orqali ishlaydi. Agar maqsadli qiymat kichikroq bo‘lsa, keyingi tekshiriladigan qiymat massivning chap yarmi markazida bo‘ladi. Bunday qidirish usulida qidiruv sohasi har doim oldingi qidiruv sohasining yarmiga teng bo‘ladi, ikkilik qidiruv algoritmining bunchalik tezligining sababi ham shunda.

Qidiruv sohasini ikkiga bo‘lish jarayoni maqsadli qiymat topilguncha yoki massivdagi qidiruv sohasi bo‘sh qolguncha davom etadi.

Qo‘lda bajarib ko‘rish

Ikkilik qidiruvni dasturlash tilida amalda amalga oshirishdan oldin, u qanday ishlashini yanada yaxshiroq tushunib olish uchun qidiruvni qo‘lda bajarib ko‘raylik. Biz 11 qiymatini qidiramiz.

1-qadam: Massivdan boshlaymiz.

2-qadam: Massiv o‘rtasidagi 3 indeksidagi qiymat 11 ga tengmi?

3-qadam: 7 soni 11 dan kichik, shuning uchun 11 ni 3 indeksining o‘ng tomonidan qidirishimiz kerak. 3 indeksining o‘ng tomonidagi qiymatlar: [ 11, 15, 25]. Keyingi tekshiriladigan qiymat — 5 indeksidagi o‘rta qiymat 15.

4-qadam: 15 soni 11 dan katta, shuning uchun 5 indeksining chap tomonidan qidirishimiz kerak. 0-3 indekslarni allaqachon tekshirganmiz, shuning uchun tekshirilmagan yagona qiymat — 4 indeksidagi qiymat.

Topdik!

11 qiymati 4 indeksida topildi.

4 indeks pozitsiyasi qaytariladi.

Ikkilik qidiruv yakunlandi.

Yuqoridagi qadamlarni animatsiyada ko‘rish uchun quyidagi simulyatsiyani ishga tushiring:

Qo‘lda bajarib ko‘rish: nima sodir bo‘ldi?

Boshida algoritmda ikkita o‘zgaruvchi bor: "left" va "right".

"left" 0 ga teng va massivdagi birinchi qiymatning indeksini ifodalaydi, "right" esa 6 ga teng va massivdagi oxirgi qiymatning indeksini ifodalaydi.

\((left+right)/2=(0+6)/2=3\) — o‘rta qiymat (7) maqsadli qiymatga (11) tengligini tekshirish uchun ishlatiladigan birinchi indeks.

7 maqsadli qiymat — 11 dan kichik, shuning uchun keyingi siklda qidiruv sohasi o‘rta qiymatning o‘ng tomoni bilan cheklanishi kerak: 4-6 indekslardagi [ 11, 15, 25].

Qidiruv sohasini cheklash va yangi o‘rta qiymatni topish uchun "left" 4 indeksiga yangilanadi, "right" esa hamon 6 ga teng. 4 va 6 — yangi qidiruv sohasidagi, ya’ni oldingi o‘rta qiymatning o‘ng tomonidagi birinchi va oxirgi qiymatlarning indekslari. Yangi o‘rta qiymat indeksi \((left+right)/2=(4+6)/2=10/2=5\).

5 indeksidagi yangi o‘rta qiymat tekshiriladi: 15 soni 11 dan katta, shuning uchun agar maqsadli qiymat 11 massivda mavjud bo‘lsa, u 5 indeksining chap tomonida bo‘lishi kerak. "right" ni 6 dan 4 ga yangilash orqali yangi qidiruv sohasi hosil qilinadi. Endi "left" ham, "right" ham 4 ga teng, \((left+right)/2=(4+4)/2=4\), shuning uchun tekshirish uchun faqat 4 indeksi qoldi. Maqsadli qiymat 11 4 indeksida topildi, shuning uchun 4 indeksi qaytariladi.

Umuman olganda, ikkilik qidiruv algoritmi maqsadli qiymat topilguncha massivdagi qidiruv sohasini aynan shu tarzda ikkiga bo‘lishda davom etadi.

Maqsadli qiymat topilganda uning indeksi qaytariladi. Agar maqsadli qiymat topilmasa, -1 qaytariladi.

Ikkilik qidiruvni amalga oshirish

Ikkilik qidiruv algoritmini amalga oshirish uchun bizga quyidagilar kerak:

1. Qidiruv olib boriladigan qiymatlarga ega massiv.
2. Qidiriladigan maqsadli qiymat.
3. Chap indeks o‘ng indeksdan kichik yoki unga teng bo‘lar ekan, bajarilaveradigan sikl.
4. O‘rta qiymatni maqsadli qiymat bilan taqqoslaydigan va maqsadli qiymat topilsa, indeksni qaytaradigan if operatori.
5. Maqsadli qiymat o‘rta qiymatdan kichik yoki katta ekanini tekshiradigan va qidiruv sohasini toraytirish uchun "left" yoki "right" o‘zgaruvchilarini yangilaydigan if operatori.
6. Sikldan keyin -1 ni qaytaring, chunki bu nuqtada maqsadli qiymat topilmaganini bilamiz.

Ikkilik qidiruv uchun natijaviy kod quyidagicha ko‘rinadi:

def binarySearch(arr, targetVal):
    left = 0
    right = len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == targetVal:
            return mid
        
        if arr[mid] < targetVal:
            left = mid + 1
        else:
            right = mid - 1

    return -1

myArray = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
myTarget = 15

result = binarySearch(myArray, myTarget)

if result != -1:
    print("Value",myTarget,"found at index", result)
else:
    print("Target not found in array.")

Ikkilik qidiruvning vaqt murakkabligi

Vaqt murakkabligi nima ekanligi haqida umumiy tushuntirish uchun ushbu sahifaga tashrif buyuring.

Insertion Sort vaqt murakkabligi haqida yanada chuqurroq va batafsil tushuntirish uchun ushbu sahifaga tashrif buyuring.

Ikkilik qidiruv har safar yangi qiymatni maqsadli qiymat ekanligini tekshirganda qidiruv sohasi ikki baravar qisqaradi.

Bu shuni anglatadiki, ikkilik qidiruv maqsadli qiymatni topa olmaydigan eng yomon holatda ham \(n\) ta qiymatli saralangan massivni ko‘rib chiqish uchun unga atigi \( \log_{2}n \) ta taqqoslash kerak bo‘ladi.

Ikkilik qidiruvning vaqt murakkabligi

\[ O( \log_{2} n ) \]

Agar ikkilik qidiruvga \(n\) ta qiymatli massivda qiymatni topish uchun qancha vaqt kerakligini chiziqli qidiruv bilan solishtirib chizsak, quyidagi grafikni olamiz:

Quyidagi ikkilik qidiruv simulyatsiyasini massivdagi qiymatlarning turli sonlari \(n\) uchun ishga tushiring va ikkilik qidiruvga maqsadli qiymatni topish uchun qancha taqqoslash kerakligini ko‘ring:

Ikkilik qidiruv simulyatsiyalarini ishga tushirganda ko‘rib turganingizdek, massiv katta bo‘lsa va biz izlayotgan qiymat topilmasa ham, qidiruv juda kam taqqoslashni talab qiladi.

For the Binary Search algorithm to work,
the array must already be .