8-Amaliy ish Qidiruv usullari: binar qidiruv, Fibonachchi qidiruv, binar daraxt bo’yicha qidiruv. Qidiruv masalasi, qidruv usullari

---

8-Amaliy ish
Qidiruv usullari: binar qidiruv, Fibonachchi qidiruv, binar daraxt bo’yicha qidiruv. 
Qidiruv masalasi, qidruv usullari. 
Rеjа: 
1.
Оddiy ko‟rib chiqish vа binаr izlаsh аlgоritmlаri 
2.
Binаr dаrахtdа izlаsh аlgоritmlаri 
3.
Rаqаmli izlаsh dаrахtlаri 
Tayanch so‘z va iboralar
: Algoritm tahlili. Boshlang„ich berilganlar sinflari. Eng yaxshi 
holat. Eng yomon holat.O„rtacha holat. O„sib borish bo„yicha saralash. Kamayish bo„yicha 
saralash. Ikkilik izlash .Ketma – ket izlash 
Ma‟lumotlar ro„yxatidan kerakli axborotni izlash nazariy programmalashning fundamental 
masalalaridan biridir. Izlash algoritmlari to„g„risida gap ketganda axborot dasturdagi berilganlar 
massividan iborat bo„lgan yozuvlarda saqlanadi degan nuqtai nazardan kelib chiqiladi.Yozuvlar 
yoki ro„yhat elementlari massivda ketma-ket joylashadi. Ko„pincha yozuvlar bir necha 
sohalardan iborat bo„lishi mumkin, ammo izlashda ushbu sohalardan faqat bittasi(kalit) hisobga 
olinadi.Yozuvlar kalit sohasi qiymati bo„yicha saralangan yoki saralanagan bo„lishi 
mumkin.Saralangan ro„yxatda yozuvlar kalitning o„sib borish tartibida joylashgan bo„lib, 
saralanmagan ro„yxatda ular tasodifiy ravishda joylashadi.Saralanmagan ro„yxatdagi izlash 
jarayoni kerakli axborotga duch kelinmaguncha barcha yozuvlarni ko„rib chiqishdan iborat 
bo„ladi. Bu eng sodda izlash algoritidir. Konkret qiymatni izlash tanlash masalasi bilan bog„liq 
bo„lib, bunda qandaydir xususiyatga ega bo„lgan elementni topish talab etiladi. Masalan, kattalik 
bo„yicha beshinchi o„rindagi element, ro„yxat oxiridan yettinchi element yoki o„rtacha qiymatli 
element. 
Ketma-ket izlash.Izlash algoritmlarida ro„yxatni maqsad elementi deb ataluvchi qandaydir 
konkret yelementni topishga qaratilgan ko„rib chtqish jarayoni amalga oshiriladi. Ketma-ket 
izlashda ro„yxat elementlari saralanmagan deb qabul qilinadi. Izlash jarayonida kerakli 
elementning ro„xatda mavjud ekanligi tekshirilibgina qolmay, balki ushbu kalitga bog„liq 
bo„lgan ma‟lumotlarga ham murojaat qilinadi.Masalan, kalitning qiymati xizatchining tartib 
nomeridan yoki boshqa identifikatordan iborat bo„lishi mukin. Kerakli kalit topilgandan so„ng 
dastur u bilan bog„liq ma‟lumotlarni o„zgartirishi yoki bosmaga chiqarishi mumkin. Umuman 
olganda, izlash algoritmining maqsadi kalitning pozitsiyasini (turgan joyini) aniqlashdan iborat. 
Agar kalit qiymat topilmasa, algoritm massivning yuqori chegarasidan katta bo„lgan indeks 
qiymatini chiqaradi. Ketma-ket izlash algoritmi ro„yhat elementlarini birinchi elementdan 
boshlab, keraklisi topilmagunga qadar birma-bir ko„rib chiqadi. Kalitning konkret qiymati 
ro„yxatda qanchalik uzoq joylashgan bo„lsa, izlashga shunchalik ko„p vaqt sarflanadi. Quyida 
ketma-ket izlash algoritmining ifodasini keltiramiz: 
Ketma_ket_Izlash(list,target,N) 
{list tekshiriluvchi ro„yxat} 
{target izlanuvchi kalit} 
{N ro„yxatdagi elementlar soni} 
For i=l to N do 
if (target=list[i]) 
return i 
end if 
end for 
return 0
 
Eng yomon holat tahlili.Ketma-ket izlash algoritmi ikki xil “eng yomon holat” variantiga 
ega. Birinchi holatda maqsad elementi ro„yxatda yeng oxirgi o„rinda joylashgan bo„ladi. 

---

Ikkinchi holatda maqsad jlementi ro„yxatda avjud bo„lmaydi. Ushbu ikki holatda nechtadan 
taqqoslash amallari bajarilishini aniqlaymiz. Agar ro„yxat elementlari takrorlanmas deb faraz 
qilsak, ro„yxatning oxirgi elementiga yetgunga qadar algoritm N ta (ro„yxat N ta elementdan 
iborat) taqqoslashni bajaradi.
Xuddi shunga o„xshash tarzda maqsad elementi mavjud bo„lmagan ro„yxatda ham algoritm N ta
taqqoslash amalini bajaradi. 
O„rtacha holat tahlili.Izlash algoritmlari uchun ikkita o„rtacha holat bo„lishi mumkin.
Birinchi holatda izlash jarayoni doimo muvaffaqiyatli tugaydi deb, faraz qilinadi. Ikkinchi 
holatda maqsad elementi mavjud bo„lmaydi. Agar maqsad elementi ro„yxatda mavjud bo„lsa, u 
mumkin bo„lgan N ta pozitsiyadan birini egallaydi. Uning bu pozitsiyalardan har birini egallash 
ehtimoli bir xil deb hisoblasak, bu ehtimol 1/N ga teng. N ta holatdan har bittasi uchun
algoritmning bajaradigan taqqoslashlari soni izlanuvchi element tartibi bilan mos tushadi. 
Natijada o„rtacha holatdagi murakkablik uchun quyidagi tenglikka ega bo„lamiz: 
( )
∑
( )
 
Agar ro„yxatda izlanuvchi element mavjud bo„lmagan holni oladigan bo„lsak, ko„rib chiqishlar 
soni
N +1 taga ortadi. Izlanuvchi element mavjud bo„lmaganda taqqoslashlar soni N ga teng 
bo„lganligidan va N ta imkoniyat ehtimoli bir xil deb olinsa, quyidagiga ega bo„linadi: 
( )
(∑
)
∑
( N juda katta bo„lganda l/(N + 1) qiymat 0 ga yaqinlashadi.)
Bundan izlanuvchi elementning ro„yxatda mavjud bo„lmasligi holati hisobga olinganda o„rtacha 
holat murakkabligi ½ ga teng miqdorda oshishi mumkinligi ko„rinadi.
Ikkilik izlash.Saralangan massivda biror elementni izlash jarayonida maqsad elementni massiv 
o„rtasidan olingan element bilan taqqoslaganda 3 ta holatdan biri yuz beradi: qiymatlar teng; 
maqsad element kichik; maqsad element katta. Birinchi holat eng yaxshi hisoblanib, izlash 
jarayoni to„xtaydi. Qolgan ikkila holatda ham massivning yarmini tashlab yuborish 
mumkin.Maqsad qiymat o„rtanchi elementdan kichik bo„lsa, u ro„yxatda o„rtancha elementdan 
oldin keladi, aks holda ushbu elementdan keyin keladi.Shu jarayonni davom ettirib, qro„yxatning 
qolgan qisining ha yarini tashlab yuboraiz va hokazo. Natijada quyidagiga ega bo„lamiz: 
Ikkilik_ket_Izlash(list,target,N 
list spisok dlya prosmotra
target selevoye znacheniye
N chislo elementov v spiske
start=1
end=N 
while start<=end do
select(compare(list[middle),target))from
case 1: start=middle+l
case 0: return middle
case 1: end=middle l
end select
end while
return 0

---

ushbu algoritmda start o„zgaruvchisiga middle o„zgaruvchisiga nisbatan 1 ga ortiq qiymat 
o„zlashtiriladi, agar maqsad qiymat topilgan o„rtacha element qiymatidan katta bo„lsa. Agar 
maqsad element qiymati o„rtacha element qiymatidan kichik bo„lsa, end o„zgaruvchisiga
middle o„zgaruvchisiga nisbatan 1 taga kam qiymat o„zlashtiriladi. Bunda sikl qanday 
ishlaydi?Agar maqsad element topilsa, return operatori ishlaydi va sikl to„xtatiladi. Agar maqsad 
element topilmasa, har bir sikl iteratsiyasida start o„zgaruvchisining qiymati ortadi yoki end 
o„zgaruvchisining qiymati kamayadi. Bu ikki o„zgaruvchining qiymatlari bir-biriga yaqinlashib 
boradi.Qaysidir qadamda bu ikki o„zgaruvchining qiymati tenglashib, start=end=middle sharti 
uchun ham sikl yana bir marta bajariladi. Shundan so„ng ushbu indeksli element maqsad element 
bo„lmasa, start ning qiymati middle va endga nisbatan 1 ga oshadi yoki aksincha end ning 
qiymati middle va start ga nisbatan 1 ga kamayadi. Ikki holatda ham while operatorining sharti 
yolg„on qiymat qabul qilib, sikl to„xtatiladi. 
O„rtacha holat tahlili. O„rtacha holatni tahlil etishda ikki imkoniyat ko„rib chiqiladi:maqsad 
elementning ro„yxatda mavjud bo„lgan holat; maqsad elementning ro„yxatda mavjud bo„lmaslik 
holati. Birinchi holatda N ta imkoniyat mavjud va ularning barchasi teng kuchli l/N ehtimolga 
ega. Bunda bajariladigan taqqoslashlarning binar daraxtidan foydalanib, quyidagi formulalarga 
ega bo„lamiz: 
( )
∑
(
)
Ushbu formulalarni qisqartirilgan holda yozsak, quyidagi ko„rinishni oladi: 
( )
N qiymati ortib borgan sari
qiymat 0 ga yaqinlashib boradi va
( )
( )
ga ega bo„lamiz. 
Иккинчи ҳолатни, яъни мақсад элементнинг рўйхатда мавжуд бўлмаслик ҳолатини кўриб 
чиқадиган бўлсак, изланган элементнинг рўйхатдаги мумкин бўлган позициялари сони N 
га тенг, аммо яна N + 1 та рўйхатдан ташқаридаги имкониятлар сони ҳам мавжуд.
Икониятлар сони N + 1 га тенг, чунки мақсад элеент ршйхатдаги биринчи элементдан 
кичик, биринчидан катта, амо иккинчидан кичик, иккинчидан катта, аммо учинчидан 
кичик ва ҳоказо токи мақсад қиймат N-элементлан катта бўлгунга қадар.Ҳар бир ҳолатда 
изланувчи элементнинг рўйхатда мавжуд эмаслиги k та таққослаш бажарилгандан кейин 
маълум бўлади. Ҳисоблашларда ҳамаси бўлиб,
2N +1 та имконият кўриб чиқилади. Шундай қилиб, қуйидагига эга бўламиз: 
( )
(∑
( ) )
( )
(
)
 
Tanlash algoritmi 
Ba‟zi holatlarda bizga ro„yxatdagi konkret qiymatga ega bo„lgan elementni emas, balki boshqa 
xususiyatga ega bo„lgan elementni izlashga to„g„ri keladi. Masalan, yozuv sohalarining kattalik 
bo„yicha k-o„rinda turgan qiymatini topish talab etilsin. Bunday yozuvni topishning usullaridan 
biri ro„yxatni kamayish tartibidan saralashdan iborat; bunda kattaliu bo„yicha k-yozuv k-o„ringa 
joylashtiriladi. Bu usul keragidan ko„proq mehnat talab qiladi: chunki izlangandan kichik 
bo„lgan elementlar bizni qiziqtirmaydi.Bu vaziyatdan chiqishning yana bir usuli mavjud: 
ro„yxatdan eng katta element topilib, ro„yxatning oxiriga joylashtiriladi.So„ngra ro„yxat qolgan 
qismining eng katta elementi topiladi va ro„yxat oxiridan ikkinchi o„ringa joylashtiriladi. Ushbu 
protsedurani K marta takrorlab, kattalik bo„yicha K-o„rinda turuvchi elementni topib olamiz: 
Tanlash(list,K,N) 

---

List ro„yxat o„zgaruvchisi 
N ro„yxat elementlari soni 
K kattalik bo„yicha tartib
For i=1 to K do 
Largest=list[1] 
LargestLocation=1 
For i=2 to N-(i-1) do 
If list[i]>largest then 
LargestLocation=j 
End if 
End for 
Swap(list[N-(i-1),list[LargestLocation]) 
End for 
Return largest 
Ushbu algoritmning murakkabligi qanday? Har bir o„tishda largest o„zgaruvchisiga ro„yxat 
birinchi elementi qiymatini o„zlashtirib, so„ngra bu o„zgaruvchi qolgan elementlar bilan 
taqqoslanadi.Birinchi o„tishda N -1 taqqoslash, ikkinchi o„tishda bittaga kam (N -2) ta 
taqqoslash va hokazo K-o„tishda N - K taqqoslashlar bajariladi.Shuning uchun kattalik bo„yicha 
K-o„rindagi eleyentni izlash uchun
∑(
)
( )
ta taqqoslashlar bajariladi.Shuni eslatib o„tish lozimki, K N /2 dan katta bo„lsa, izlashni ro„yxat 
oxiridan boshlagan ma‟qul. K ning 1 yoki N ga yaqin qiymatlari uchun ushbu algoritm 
anchagina eqqektiv hisoblansa, ro„yxat o„rtasidagi qiyatlar uchun yanada unumdor algoritmlar 
mavjud.Bizga faqat kattalik bo„yicha K-tartibli element kerak bo„lgani uchun izlangan 
elementdan katta elementlarning o„rni bizni qiziqtirmaydi. Ro„yxatdan olingan har bir element 
uchun ro„yxat ikki qismga ajraladi: berilgan elementdan kattalari va kichiklari.Ro„yxat 
elementlarini tanlangan elementdan oldin faqat undan kichiklari,keyin esa faqat undan kattalari 
joylashadigan qilib, qayta saralasak, shu bilan birga tanlangan element R-o„rinda joylashsa, 
uning kattalik bo„yicha R-element ekanligi aniqlanadi.Ro„yxatni bunday qayta saralash 
tanlangan elementni qolganlari bilan taqqoslab chiqishni talab etadi. Bunda R- 1 taqqoslash 
bajariladi. Ushbu rekursiv algoritm quyidagi ko„rinishga ega: