2-Laboratoriya ishi. Mavzu: Binar qidiruv. Qidiruv


Bu algoritm qanday ishlashini ko’rib chiqamiz



Download 193,83 Kb.
bet2/3
Sana31.12.2021
Hajmi193,83 Kb.
#246486
1   2   3
Bog'liq
Binar Qidiruv

Bu algoritm qanday ishlashini ko’rib chiqamiz:

  • Hamisha bizda uchta son mavjud: bular element izlayotgan massiv indekslari chegarasi: L(left, chap) va R(right, ong) indekslar va izlanayotgan x soni; Dastlab L=1, R = n+1; O’ng index tegishlli emas. Ya’ni dastlab sonni butun massivdan izlaymiz. O’ng (right) chegara massivdan o’ng tomondagi birinchi indeks va u berilgan massivga tegishli emas.



  • Har safar berilgan kesma o’rtasidagi elementni tanlaymiz va uni izlanayotgan element bilan taqqoslaymiz.

  • O’rtasagi element indeksi esa quyidagiga teng: m = (L+R) / 2;

  • Agar o’rtadagi element izlanayotgan sondan katta bo’lsa qidiruvni o’ng tamondan chegaralaymiz. l Chunki massiv kamaymaslik tartibda saralangani uchun o’rtadagi element iznanayotgan sondan katta bo’lganligi sababli undan o’ng tamondagi barcha sonlar izlanayotgan sondan katta bo’ladi va ularning bizga endi keragi bo’lmaydi. Izlanayotgan interval [L, m] ga o’tadi.

  • Aks holda chap tamondan chegaralayzim. Izlanayotgan interval [m, R] ga o’tadi.

  • Demak harbir amalda izlanayotgan interval uzunligi 2 marta kamayadi. Har bir amalda 2 marta kamaysa u holda k ta amaldan so’ng 2k marta kamayadi. Dastlab interval uzunligi n ga teng bo’lganligi uchun uning 1 gacha kamayishi uchun ketadigan amallar sonini esa quyidagich aniqlaymiz.

2k=n => k=log2(n). Ya’ni umumiy amallar soni log(n) ga teng bo’ladi. Bu asa n ning qiymati 105 atrofida bo’lganda taxminan 17 ga teng bo’ladi. Demak binar qidiruv algoritmida har bir izlash haqidagi so’rovga shuncha amal bajarish orqali javob berish mumkin.

Masalan 22 sonini qidiraylik:

1) O’rtadagi element 17 ga teng, 22≥17 bo’lganligi uchun uni o’ng tamondan izlashni davom ettiramiz.

2) Endi o’rtadagi element 30 ga teng. 22<30 bo’lganligi uchun endi uni chap tomondan izlaymiz.



3) Bu safar o’rtadagi element 22 ga teng 22≥22 bo’lganli uchun endi izlashni o’ng tomondagi intervaldan davom ettiramiz.



4) O’rtadagi element 25, 22<25 bo’lganligi uchun intervalni chap tomondan davom ettiramiz.



Nihoyat izlanayotgan intervalning chegaralari bir yerga kelib qoldi ya’ni R=L+1 bo’ldi. R indeksni dastlab massivga tegishli bo’lmagan indeks qilib oldik. Izlanayotgan massiv indeksi L o’zgaruv bo’ladi. Biz bu indeksni topdik, lekin iznalayotgan son massivda yo’q bo’lishi mumkin. Buni tekshirish uchun esa topilgan indeksdagi massiv elementining izlanayotgan songa tengligini tekshirish yetarli bo’ladi ya’ni ya’ni if (a[L]==x).


1   2   3




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish