Binar qidirish



Download 270,18 Kb.
bet1/4
Sana29.11.2022
Hajmi270,18 Kb.
#874190
  1   2   3   4
Bog'liq
SAYFIYEV JAVOHIR ZAMONAVIY DASTURLASH TILLARI

TOSHKENT DAVLAT PEDAGOGIKA UNIVERSITETI SAYFIYEV JAVOHIR

ZAMONAVIY DASTURLASH TILLARI FANIDAN MUSTAQIL TA’LIMI

Binar qidirish

  • Binar qidirish — (eng: Binary search — ikkilik qidirish)- saralangan elementlar roʻyxatidan elementni topish uchun samarali algoritm. Ikkilik qidirish algoritmi ishlash gʻoyasiga koʻra „boʻlib tashla va hukmronlik qil“ paradigmasi asosida ishlaydi.

 Ikkilik qidiruvdan foydalanishning eng keng tarqalgan usullaridan biri bu massivdagi elementni topishdir. Misol uchun, Tycho-2 yulduzlar katalogida bizning galaktikamizdagi eng yorqin 2 539 913 ta yulduz haqida maʼlumot mavjud. Aytaylik, siz yulduz nomidan kelib chiqib, katalogdan maʼlum bir yulduzni qidirmoqchisiz

  •  Ikkilik qidiruvdan foydalanishning eng keng tarqalgan usullaridan biri bu massivdagi elementni topishdir. Misol uchun, Tycho-2 yulduzlar katalogida bizning galaktikamizdagi eng yorqin 2 539 913 ta yulduz haqida maʼlumot mavjud. Aytaylik, siz yulduz nomidan kelib chiqib, katalogdan maʼlum bir yulduzni qidirmoqchisiz

Agar dastur yulduzlar katalogidagi har bir yulduzni birinchisidan boshlab, chiziqli qidiruv algoritmida tekshirgan boʻlsa, eng yomon holatda kompyuter siz izlayotgan yulduzni topish uchun barcha 2 539 913 ta yulduzni tekshirishi kerak boʻlishi mumkin. Agar katalog yulduz nomlari boʻyicha alifbo tartibida tartiblangan boʻlsa, ikkilik qidiruv, hatto eng yomon holatda ham 22 dan ortiq yulduzni tekshirishi shart emas edi.

  • Agar dastur yulduzlar katalogidagi har bir yulduzni birinchisidan boshlab, chiziqli qidiruv algoritmida tekshirgan boʻlsa, eng yomon holatda kompyuter siz izlayotgan yulduzni topish uchun barcha 2 539 913 ta yulduzni tekshirishi kerak boʻlishi mumkin. Agar katalog yulduz nomlari boʻyicha alifbo tartibida tartiblangan boʻlsa, ikkilik qidiruv, hatto eng yomon holatda ham 22 dan ortiq yulduzni tekshirishi shart emas edi.
  • 1. Chiziqli qidiruv algoritmi
  • Bu qidiruv algoritmining asosiy g’oyasi – massivning barcha elementlarini qidirilayotgan kalit-qiymat bilan ketma-ket taqqoslab chiqish va topilgan elementning joylashgan pozitsiyasini qaytrishdan iborat. Shuning uchun ham bu qidiruv usuli odatda ketma-ket qidiruv deb ataladi.
  • Bu usulda qidiruv algoritmining ish samaradorligi juda past.
  • Bu algoritmni namunaviy misol yordamida o’rganib chiqamiz. Misol. Tasodifiy sonlar bilan to’ldirilgan massivdan oldindan berilgan kalit-qiymatli elementning joylashgan pozitsiyasi (indeksi)ni aniqlang.
  • Yechimi:
  • Yechimi:
  • Buning uchun butun sonli arr[] massivini tavsiflab, uni tasodifiy sonlar generatori rand() funktsiyasi yordamida qiymatlarga to’ldiramiz (misol uchun 50 ta butun son bilan).
  • Klaviaturadan kiritilgan kalit-qiymatga teng bo’lgan qiymatga teng element massivda bor yoki yo’qligini aniqlash funktsiyasi linSearch() ni tavsiflaymiz.


Download 270,18 Kb.

Do'stlaringiz bilan baham:
  1   2   3   4




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