Axborot tizimlari va texnologiyalari kafedrasi m ustaqil ta’lim mavzu

O’ZBEKISTON RESPUBLIKASI OLIY VA O’RTA MAXSUS TA’LIM
VAZIRLIGI
NIZOMIY NOMIDAGI TDPU
PROFESSIONAL TA’LIM FAKULTETI
AXBOROT TIZIMLARI VA TEXNOLOGIYALARI KAFEDRASI
M
USTAQIL TA’LIM

MAVZU: QIDIRUV USULLARI: BINAR QIDIRUV, FIBONACHI QIDIRUV, BINAR DARAXT BO’YICHA QIDIRUV. TAKRORLANUVCHI ALGORITMGA DOIR MISOL ISHLAB CHIQISH

BAJARDI: Xusanboev Elmurod

TEKSHIRDI: PRIMKULOVA ALIMA
Mavzu: Qidiruv usullari: Binar qidiruv, Fibonachi qidiruv, Binar daraxt bo’yicha qidiruv. Takrorlanuvchi algoritmga doir misol ishlab chiqish
Reja:

1. 
   Binar qidiruv suli;
   
2. 
   Fibonachi qidiruv usuli;
   
3. 
   Takrorlanuvchi algoritmga doir misollar;
   

Binar (ikkilik) qidiruv

Binar (ikkilik, dichotomik) qidiruv-bu to'plamning ikki qismga bo'linib, kerakli element ushbu qismlardan biriga kiradigan tarzda amalga oshiriladigan buyurtma majmuasida berilgan elementni izlashdir. Qidiruv element element bilan mos kelganda tugaydi, bu to'plamning qismlari orasidagi chegara yoki kerakli element yo'q bo'lganda.
Binar qidiruv tartiblangan to'siqlarga qo'llaniladi va ketma-ketlikni yarmiga ajratish va elementni har bir iteratsiya bo'yicha faqat bir yarimda topishdir.
Shunday qilib, ushbu usulning g'oyasi quyidagicha. Tartibli qator elementlari orasida kerakli qiymatni qidirish (ortib borayotgan yoki kamayib borayotgan) bu qatorning Markaziy elementining qiymatini aniqlash bilan boshlanadi. Ushbu elementning qiymati kerakli qiymat bilan taqqoslanadi va taqqoslash natijalariga qarab muayyan harakatlar amalga oshiriladi. Agar kerakli va Markaziy qiymatlar teng bo'lsa, qidiruv muvaffaqiyatli yakunlanadi. Agar kerakli qiymat Markaziy yoki undan kam bo'lsa, unda markazning chap yoki o'ng tomonidagi elementlardan tashkil topgan qator hosil bo'ladi. So'ngra qidiruv yangi qator takrorlanadi ( guruch. 37.1).
Binar qidiruv algoritmi
Qadam 1. O'rta qatorning o'rta elementining sonini aniqlang=(yuqori+past) / 2
2-bosqich. Agar qator o'rtacha element qiymati kerakli teng bo'lsa, keyin qiymati qaytadi, kerakli element soniga teng, va algoritm ishini yakunlaydi.
3 qadam. Kerakli qiymati o'rtacha element qiymati katta bo'lsa, keyin o'rta o'ngdagi barcha elementlar bir qator sifatida olib, aks holda o'rta chap barcha elementlar bir qator sifatida olib (buyurtma tabiatiga qarab). 1 qadamiga o'taylik.
Qator qadriyatlar bilan bir necha elementlarni duch mumkin, kaliti teng. Bu algoritm asosiy element bilan mos birinchi topadi, qator quyidagi tartibda birinchi bo'lishi mumkin, yoki teng kalit orasida oxirgi. Masalan, raqamlar qatorida 1, 5, 5, 5, 5, 5, 5, 7, 8 key =5 tugmachasi bilan element 4 tartib raqamiga mos keladi, bu ham birinchi, ham ikkinchisiga taalluqli emas.
B
irinchi va oxirgi kirishni topish uchun ushbu algoritmning ikkita modifikatsiyasi mavjud. Bularning barchasi o'rta elementning qanday tanlanishiga bog'liq: kichik yoki katta tomonga yaxlitlash. Birinchi holda, o'rtacha element qator chap anglatadi, va ikkinchi-o'ng.
Shakl. 37.1. Binarqidiruv algoritmini namoyish qilish.
// Binar qidiruv funktsiyasi tavsifi
int BinarySearch(int *x, int k, int key){
bool found = false;
int high = k - 1, low = 0;
int middle = (high + low) / 2;
while ( !found && high >= low ){
if (key == x[middle])
found = true;
else if (key < x[middle])
high = middle - 1;
else
low = middle + 1;
middle = (high + low) / 2;}
return found ? middle : -1 ;}
Binar qidiruv algoritmining ishlash jarayonida ushbu qidiruvni davom ettirish kerak bo'lgan qismning hajmi har safar taxminan ikki barobar kamayadi. Bu algoritmning murakkabligini O(log n) ga moslashtiradi, bu erda n – to'siq elementlarining soni.
Binar qidiruv algoritmining ish vaqti: agar funktsiya haqiqiy dalilga ega bo'lsa, \varepsilon aniqligi bilan \log\frac{1}{\varepsilon} vaqtida yechim toping va agar argument alohida bo'lsa, unda echim izlash 1 + log n vaqtni oladi.
Ushbu algoritmning afzalligi-ketma-ket qidiruv algoritmiga nisbatan qidiruvni amalga oshirishning nisbatan tezligi. Salbiy tomoni shundaki, ikkilik qidiruv faqat tartiblangan tartibda qo'llanilishi mumkin.
Asosiy shartlar
Binar (ikkilik, dichotomik) qidiruv-bu to'plamning ikki qismga bo'linib, kerakli element ushbu qismlardan biriga kiradigan tarzda amalga oshiriladigan buyurtma majmuasida berilgan elementni izlashdir.
Qidiruv kaliti-bu qidiruv qiymati bo'yicha yozilgan maydon
Qidiruv-ilgari yaratilgan ma'lumotlar majmuasida aniq ma'lumotni topish jarayoni.
To'siqni qidirish-chegara elementini aniqlash orqali jarayonni tezlashtiradigan ketma-ket qidiruv algoritmining modifikatsiyasi.