Binar qidirish

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.