Binar qidiruv
Ikkilik qidiruv
Ikkilik qidiruv algoritmi tartiblangan massiv bo‘ylab izlaydi va izlayotgan qiymat indeksini qaytaradi.
{{ msgDone }}
Ikkilik qidiruv algoritmi qanday ishlashini ko‘rish uchun simulyatsiyani ishga tushiring.
Ikkilik qidiruv chiziqli qidiruvga qaraganda ancha tezroq, lekin ishlashi uchun tartiblangan massiv kerak.
Ikkilik qidiruv algoritmi massiv markazidagi qiymatni tekshirish orqali ishlaydi. Agar maqsadli qiymat pastroq bo‘lsa, tekshirish uchun keyingi qiymat massivning chap yarmining markazida bo‘ladi. Qidiruvning bu usuli qidiruv maydoni har doim oldingi qidiruv maydonining yarmi ekanligini bildiradi va shuning uchun Ikkilik qidiruv algoritmi juda tezdir.
Qidiruv maydonini yarmiga qisqartirish jarayoni maqsadli qiymat topilgunga qadar yoki massivning qidirish maydoni bo‘sh bo‘lgunga qadar sodir bo‘ladi.
Qanday ishlaydi:
- Massivning markazidagi qiymatni tekshiring.
- Agar maqsadli qiymat pastroq bo‘lsa, massivning chap yarmini qidiring. Maqsadli qiymat yuqoriroq bo‘lsa, o‘ng yarmini qidiring.
- Maqsadli qiymat topilmaguncha yoki qidiruv maydoni bo‘sh qolguncha massivning yangi qisqartirilgan qismi uchun 1 va 2-bosqichlarni davom ettiring.
- Agar qiymat topilsa, maqsadli qiymat indeksini qaytaring. Agar maqsadli qiymat topilmasa, -1ni qaytaring.
Qo‘lda yugurish
Keling, Python dasturida amalda qo‘llashdan oldin Ikkilik qidiruv qanday ishlashini yaxshiroq tushunish uchun qidiruvni qo‘lda bajarishga harakat qilaylik. Biz 11 qiymatini qidiramiz.
1-qadam: Biz massivdan boshlaymiz.
[ 2, 3, 7, 7, 11, 15, 25]
2-qadam: 3-indeksdagi massivning o‘rtasida joylashgan qiymat 11 ga tengmi?
[ 2, 3, 7, 7, 11, 15, 25]
3-qadam: 7 11 dan kichik, shuning uchun biz 3 indeksning o‘ng tomonida 11 ni qidirishimiz kerak. 3 indeksining o‘ng tomonidagi qiymatlar [ 11, 15, 25]. Tekshirish uchun keyingi qiymat 5 indeksdagi o‘rta qiymat 15 hisoblanadi.
[ 2, 3, 7, 7, 11, 15, 25]
4-qadam: 15 11 dan yuqori, shuning uchun biz 5-indeksning chap tomonida qidirishimiz kerak. Biz allaqachon 0-3 indeksini tekshirdik, shuning uchun indeks 4 faqat tekshirish uchun qoldi.
[ 2, 3, 7, 7, 11, 15, 25]
Biz topdik!
11-qiymat 4-indeksda topilgan.
Returning index position 4.
Ikkilik qidiruv tugallandi.
Yuqoridagi animatsiyali qadamlarni ko‘rish uchun quyidagi simulyatsiyani bajaring:
Pythonda ikkilik qidiruvni amalga oshirish
Ikkilik qidiruv algoritmini amalga oshirish uchun bizga kerak:
- Qidiruv uchun qiymatlarga ega massiv.
- Qidiriladigan maqsadli qiymat.
- Chap indeks o‘ng indeksdan kichik yoki unga teng bo‘lgan vaqtgacha ishlaydigan sikl.
- O‘rta qiymatni maqsadli qiymat bilan taqqoslaydigan va agar maqsadli qiymat topilsa, indeksni qaytaradigan if-iborasi.
- Maqsadli qiymat o‘rta qiymatdan kichik yoki kattaroq ekanligini tekshiradigan va qidiruv maydonini toraytirish uchun "chap" yoki "o‘ng" o‘zgaruvchilarni yangilaydigan if-iborasi.
- Loopdan keyin -1 ni qaytaring, chunki bu nuqtada biz maqsadli qiymat topilmaganini bilamiz.
Ikkilik qidiruv uchun natija kodi quyidagicha ko‘rinadi:
Misol
Python da ikkilik qidiruv algoritmini yarating:
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
mylist = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
x = 11
result = binarySearch(mylist, x)
if result != -1:
print("Found at index", result)
else:
print("Not found")
Misolni ishga tushirish »
Ikkilik qidiruv vaqtining murakkabligi
Ikkilik qidiruv har safar yangi qiymatni maqsadli qiymat yoki yo‘qligini tekshirganda, qidiruv maydoni ikki baravar kamayadi.
Bu shuni anglatadiki, Ikkilik Qidiruv maqsadli qiymatni topa olmaydigan eng yomon holatda ham, \(n\) qiymatlarning tartiblangan massivini ko‘rib chiqish uchun unga faqat \( \log_{2}n \) solishtirish kerak bo‘ladi.
Ikkilik qidiruv uchun vaqt murakkabligi: \( O( \log_{2} n ) \)
Eslatma: Big O notatsiyasidan foydalangan holda vaqt murakkabligini yozishda biz shunchaki \( O( \log n ) \) yozishimiz mumkin edi, lekin \( O( \log_{2} n ) \) har bir yangi taqqoslash uchun massiv qidirish maydoni ikki baravar kamaytirilishini eslatib turadi, bu ikkilik qidiruvning asosiy tushunchasi, shuning uchun biz bu holatda faqat 2 ta asosiy ko‘rsatkichni saqlab qolamiz.
Agar chiziqli qidiruv bilan solishtirganda \(n\) qiymatlar massivida qiymatni topish uchun Ikkilik qidiruv qancha vaqt kerakligini chizsak, quyidagi grafikni olamiz:
W3Schools Pathfinder
Yutuqlaringizni kuzating – bu bepul!