Informatika fanida binar qidiruv, shuningdek, yarim intervalli qidiruv, logarifmik qidiruv yoki binar chop deb nomlanuvchi qidiruv algoritmi boʻlib, tartiblangan massiv ichida maqsadli qiymatning oʻrnini topadi

O'ZBЕKISTON RESPUBLIKASI AXBOROT TEXNOLOGIYALARI VA
KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI


MUHAMMAD AL-XORAZMIY NOMIDAGI
TOSHKЕNT AXBOROT TЕXNOLOGIYALARI UNIVЕRSITЕTI

Ma’lumotlar tuzilmasi va algoritmlar

fanidan Mustaqil ish - 1
Topshirdi :Xaliljonov Izzatulla


Toshkent- 2022

Mavzu: 1Binar qidiruv

Variant - 12

Informatika fanida binar qidiruv, shuningdek, yarim intervalli qidiruv, logarifmik qidiruv yoki binar chop deb nomlanuvchi qidiruv algoritmi boʻlib, tartiblangan massiv ichida maqsadli qiymatning oʻrnini topadi. Binar qidiruv maqsadli qiymatni massivning oʻrta elementi bilan solishtiradi. Agar ular teng bo'lmasa, nishon yotolmaydigan yarmi yo'q qilinadi va qolgan yarmida qidirish davom etadi, yana o'rta elementni maqsad qiymati bilan taqqoslash uchun olib, maqsadli qiymat topilguncha takrorlanadi. Agar qidiruv qolgan yarmi bo'sh bo'lishi bilan tugasa, maqsad massivda emas.

Binar qidiruv logarifmik vaqt ichida eng yomon holatda ishlaydi, bunda {\displaystyle O(\log n)}O(\log n) taqqoslash mumkin, bunda {\displaystyle n}n massivdagi elementlar soni.[a][ 6] Binar qidiruv chiziqli qidiruvga qaraganda tezroq, kichik massivlardan tashqari. Biroq, Binar qidiruvni qo'llash uchun massiv avval tartiblangan bo'lishi kerak. Tez qidirish uchun mo'ljallangan maxsus ma'lumotlar tuzilmalari mavjud, masalan, xesh-jadvallar, ularni Binar qidiruvdan ko'ra samaraliroq qidirish mumkin. Shu bilan birga, Binarqidiruv kengroq muammolarni hal qilish uchun ishlatilishi mumkin, masalan, massivda bo'lmasa ham, maqsadga nisbatan massivdagi keyingi eng kichik yoki keyingi eng katta elementni topish.

Binar qidiruvning ko'plab variantlari mavjud. Xususan, kasrli kaskad bir nechta massivlarda bir xil qiymat uchun Binar qidiruvlarni tezlashtiradi. Fraksiyonel kaskad hisoblash geometriyasi va boshqa ko'plab sohalarda bir qator qidiruv muammolarini samarali hal qiladi. Eksponensial qidiruv Binar qidiruvni cheklanmagan ro'yxatlargacha kengaytiradi. Binar qidiruv daraxti va B-daraxt ma'lumotlar tuzilmalari Binar qidiruvga asoslangan.