O‘zbekiston respublikasiaxborot texnologiyalari va

O‘ZBEKISTON RESPUBLIKASIAXBOROT TEXNOLOGIYALARI VA
KOMMUNIKATSIYALARINI RIVOJLANTIRISH VAZIRLIGI

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI SAMARQAND FILIALI

"Axborot texnalogiyasi" kafedrasi
2-Amaliy mashg’uloti bo’yicha.

Fan_______Ma’lumotlar tuzulmasi va Algoritm (A)____________

Guruh:_______21-04_________
Talaba : Mehriddinov Asliddin_
Rahbar:__ Eshanqulov U.L.__

Samarqand-2023

2-Amaliy mashg’uloti bo’yicha.
Mavzu: Ketma-ket qidiruv usuli orqali 1 dan n gacha bo’lgan sonlar ichidan ixtiyoriy elenementni topish dastur
1. Ishdan maqsad;

2. 
   Mavzu bo’yicha qisqacha tushunchalar;
   
3. 
   Masalani yechish (algoritm, dastur kodi, natija);
   
4. 
   Xulosa;
   
5. 
   Foydalanilgan adabiyotlar.
   

Nazariy qismi.
Mavzu bo’yicha qisqacha tushunchalar.
Binar qidirish — (eng: Binary search — ikkilik qidirish)- saralangan elementlar roʻyxatidan elementni topish uchun samaralialgoritm. Ikkilik qidirish algoritmi ishlash gʻoyasiga koʻra „boʻlib tashla va hukmronlik qil“paradigmasiasosida ishlaydi. Ikkilik qidiruvdan foydalanishning eng keng tarqalgan usullaridan biri bu massivdagi elementni topishdir. Misol uchun, Tycho-2 yulduzlar katalogida bizninggalaktikamizdagieng 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.

Binary Search
Binar qidirish algoritmi ishlash prinsipi[tahrir|manbasini tahrirlash]
Ikkilik qidirish algoritmining ishlashini tushunish uchun kompyuter bilan oʻyin oʻynab koʻramiz.
Buning uchun eng kam qadamda topish algoritmi qaysi?
Birinchi navbatda oʻrtadagi sonni taxmin qilib koʻramiz, yaʼni 50 ni. Aytaylik kompyuter bizga taxminimiz kompyuter tanlagan sondan kichikroq ekanligini aytdi. Endi biz kompyuter tanlagan son 51 va 100 orasidagi son ekanligini bilamiz. Shunday qilib, bizning qidirish sohamiz ikki baravarga qisqaradi (50 ta son). Huddi shu tarzda davom etamiz. Endi 51 dan 100 gacha sonlar oʻrtasidagi sonni olamiz, yaʼni 75 ni. Kompyuter bizga 75 tanlangan sondan katta ekanligini aytdi. Demak, 75 dan katta barcha sonlar ham tanlangan sondan katta ekan. Shunday qilib, bizdagi qidirish sohasi yana ikki baravarga qisqardi (25 ta son). Huddi shunday davom etib, biz oʻylangan sonni topishimiz mumkin. Sonlar 100 ta boʻlgan holatda, biz har qanday tahminni koʻpi bilan 7 ta qadamda topishimiz mumkin boʻladi.
Mazkur funksiyaning vazifasi shundan iboratki, u berilgan kalit bo’yicha daraxt tuguni qidiruvini amalga oshiradi. Qidiruv operatsiyasining davomiyligi daraxt tuzilishiga bog’liq bo’ladi. Haqiqatdan, agar elementlar daraxtga kalit qiymatlari o’sish (kamayish) tartibida kelib tushgan bo’lsa, u holda daraxt 5.7-rasmdagidek bir tomonga yo’nalgan ro’yhat hosil qiladi (chiqish darajasi bir bo’ladi, ya’ni yagona shoxga ega), masalan:

Bir tomonlama yo’naltirilgan binar daraxt tuzilishi
Bu holda daraxtda qidiruv vaqti, bir tomonlama yo’naltirilgan ro’yhatdagi kabi bo’lib, o’rtacha qarab chiqishlar soni N/2 bo’ladi. Agar daraxt muvozanatlangan bo’lsa, u holda qidiruv eng samarali natija beradi.Bu holda qidiruv dan ko’p bo’lmagan elementlarni ko’rib chiqadi.