Ikkilik qidirish (Binary search) C# - Информатика и ИТ - Курсовые работы

Информация о документе

Цена	35000UZS
Размер	306.3KB
Покупки	0
Дата загрузки	29 Май 2025
Расширение	docx
Раздел	Курсовые работы
Предмет	Информатика и ИТ

Продавец

Telzor Uchun

Дата регистрации 21 Апрель 2025

24 Продаж

Ikkilik qidirish (Binary search) C#

Купить

O’ZBEKISTON RESPUBLIKASI OLIY VA O’RTA
MAXSUS TA’LIM VAZIRLIGI
URGANCH DAVLAT UNIVERSITETI
“FIZIKA-MATEMATIKA” FAKULTETI
“AXBOROT TEXNOLOGIYALARI” KAFEDRASI “AXBOROT TEXNOLOGIYASI VA
DASTURLASH” FANIDAN KURS ISHI.
Mavzu : ”Ikkilik qidirish (Binary search)”
5130300 – “ Matematik injinering (Ishlab chiqarish sohalari boyicha)”
Bajardi : 1-kurs Shomuratova Shahzoda Shavkat qizi
Ilmiy rahbari:_________________________________________________
Topshirgan sanasi:_____________________________________________
Himoya qilgan sanasi: __________________________________________
Baho: _______________________________________________________
1

Urganch – 2023- yil
MUNDARIJA
KIRISH..................................................................................................................3
I.BOB. DASTURLASH NIMA?................................................................................4
1.1.C# DASTURLASH TILINING MAQSAD VA VAZIFALARI.....................................4
1.2. VIZUAL STUDIO MUHITINI SOZLASH.............................................................6
II. BOB. MA'LUMOTLARNI QIDIRISH....................................................................7
2.1.CHIZIQLI QIDIRISH VA IKKILIK QIDIRISH O'RTASIDAGI FARQ..........................8
2.2."BO'LIB TASHLA VA HUKMRONLIK QIL" PARADIGMASI...............................19
XULOSA .............................................................................................................21
FOYDALANILGAN ADABIYOTLAR.......................................................................22
2

KIRISH
XX asrning 80 - yillaridan oldin ishlab chiqilgan kompyuterlar uchun katta
dasturiy sistemalarni ishlab chiqish juda ham mushkul vazifa edi. Buning
eng katta sababi shu davrga xos bo’lgan kompyuterlarning imkoniyatlarining
chegaralanganidandir. Dasturiy komplekslarni ishlab chiqishda asosiy
cheklanishlar kompyuter tezkor xotirasining sig’imi, ma’lumotlarini
ikkilamchi xotira qurilmalaridan ( magnit lentalar , barabanlar va x.k.)
o’qish tezligi , protsessorning ishlash tezligi ( ularning takt chastotalari
bir necha yuz mikrosekund bo’lgan) bilan bog’liq. Bu davrdagi kompyuterlar
xalq ho’jaligining hisob-kitob bilan bog’liq bo’lgan masalalarini yechish uchun
mo’ljallangan edi. Kompyuterlarda boshqa xarakterdagi masalalarning
yechishni iloji yo’q edi. Dasturchilar uchun shu kompyuterlarda yechilayotgan
masala uchun berilgan ma’lumotlarni hisobga olgan holda masalani yechish
algoritmini ishlab chiqish birinchi o’rindagi vazifa hisoblangan . Bu borada N.
Virtning mashhur ma’lumotlar + algoritm = dasturformulasini yodga olish
yetarli. 80-yillardan keyin ishlab chiqilgan kompyuterlarning
imkoniyatlari kengayib, ishlab chiqarish narxi keskin pasaygani tufayli
ulardan foydalanish samarasi ortib bordi. Natijada, dastlab matn va
grafiklar uchun muharrirlari ishlab chiqildi, keyinchalik multimedia
qurilmasi yordamida tovushli ma’lumotlarni qayta ishlash imkoniyatlari
ham paydo bo’ldi. Kompyuter tasviriy imkoniyatlarining kengayishi
foydalanuvchilar uchun qulay bo’lgan grafik muloqot interfeysini yaratilishiga
sabab bo’ldi. Natijada yuqori murakkablikdagi katta amaliy dasturlarni yaratish
foydali hamda zarur bo’lib qoldi. Dasturiy vositalarni ishlab chiqish uchun qurol
sifatida yuqori bosqichli algoritmik tillardan foydalanildi. Bu dasturiy
3

vositalar dasturchi va dasturchilar guruhi imkoniyatlarini kengaytirib, dasturiy
mahsulotlarning murakkablik darajasining ortishiga ham sabab bo’ldi.
I BOB. DASTURLASH NIMA?
"Dasturlashning eng asosiy muammosi — bu murakkablik. Murakkablikni hal
qilishning faqatgina bitta asosiy yo'li bor: Bo'lib tashla va hukmronlik qil" —
Bjarne Stroustrup yodda tutish juda muhim! Algoritm faqat tartiblangan massiv
bilan to'g'ri ishlaydi. Va agar tasodifan siz uni ishlatishdan oldin qatorni
saralashni unutgan bo'lsangiz, unda ko'p hollarda algoritm hisoblangan javob
noto'g'ri bo'ladi.
1.1 C# DASTURLASH TILINING MAQSAD VA VAZIFALARI.
Hozirgi kunda C# dasturlash tili yuqori bosqichli dasturlash tillari ichida eng
samarali dasturlash tillaridan hisoblanadi. C# dasturlash tilida dastur tuzish
uchun Visual Studio.NET muhitidan foydalanamiz. C# dasturlash tili obyektga
mo’ljallangan dasturlash tili hisoblanadi. Ushbu qo’llanmada C# dasturlash tili
va uning operatorlari haqida ma’lumotlar keltirilgan.
Bilamizki ma’lumotlarni oqish va yozish turli xil oqimlar orqali amalga oshiriladi.
Ma’lumotlarni fayl oqimlari orqali o’qish va yozish juda katta ahamiyatga ega.
Sababi agar bir ma’lumotlarni ekran orqali o’qisak va yozsak unda har safar
dasturni ishga tushirganda ma’lumotlarni qaytadan kiritishga to’g’ri keladi bu
esa ancha qiyinchiliklar tug’diradi. Bundan tashqari natijalarni tahlil qilishda,
ularni solishtirishda ham fayl oqimi bilan ishlash juda ko’p qulayliklarni olib
keladi. Birinchi bobda Console rejimda ma’lumotlarni ekran orqali kiritish va
chiqarish amallari ko’rib chiqilgan. C# tilining sintaksisi, ma’lumotlar tiplari
haqida ma’lumotlar keltirilgan. Har bir operatorning funksional
imkoniyatlari misollar orqali tushuntirib berilgan. C# tilida ifoda, instruksiya
4

va operatorlar haqida ma’lumotlar keltirilgan. Tarmoqlash, takrorlash
operatorlari va ularni har xil variantlari misollar orqali tushuntirib berilgan.
Bundan tashqari har bir operatorning funksional imkoniyatlari misollar orqali
tushuntirib berilgan. Obyektga mo’ljallangan dasturlash tillarining asosini sinf
tashkil qiladi. Qo’llanmaning ikkinchi bobi Microsoft Visual Studio 2010
muhitida C# dasturlash tili yordamida fayllar bilan ishlash, ular ustida
bajariladigan amallarga bag’ishlangan. Bunda fayl va kataloglar ro’yxati
ustida bajariladigan barcha metodlar o’rganib chiqilgan. Bunda fayl va
kataloglar ustida bajariladigan metodlar o’rganilib misollar orqali
tushuntirib berilgan. Ma’lumotlarni faylda yozish va o’qish oqimlari bo’yicha
mavjud metodlar o’rganilib misollar orqali tushuntirib berilgan. Har bir
operatorning funksional imkoniyatlari misollar orqali tushuntirib berilgan.
Visual Studio.NET sistemasida dasturni kompilyatsiya qilish va bajarishning bir
necha usuli bor. Ko’p hollarda dasturchilar dasturni alohida kompilyatsiya qilib
bir nechta klavishalar kombinatsiyalari orqali ishlatishga o’rganishgan.
<Ctrl>+<Shift>+<B> tugmalarini bosish orqali yoki menyuning Build -> Build
Solution qismini tanlash orqali dasturni kompilyatsiya qilish mumkin.
Alternativ variant sifatida instrumentlar panelidagi Build tugmasini bosish
ham mumkin.
Dasturni kompilyatsiya qilmasdan ishlatish uchun <Ctrl> + <F5> tugmasini yoki
menyuning Debug -> Start Without Debugging qismini tanlash yoki panel
instrumentlar qismidagi mos tugmani bosish lozim.
using System;
class Hello
{
5

static void Main(string[] args)
{
Console.WriteLine(“Hello”);
}
}
1.2 VIZUAL STUDIO MUHITINI SOZLASH.
Microsoft Visual Studio bu birlashgan rivojlanish muhiti (IDE) dan Microsoft. Bu
rivojlanish uchun ishlatiladigan kompyuter dasturlari, shu bilan birga veb-
saytlar, veb-ilovalar, veb-xizmatlar va mobil ilovalar. Visual Studio kabi
Microsoft dasturiy ta'minotini ishlab chiqish platformalaridan foydalanadi
Windows API, Windows shakllari , Windows taqdimot fondi, Windows
do'koni va Microsoft Silverlight. U ikkalasini ham ishlab chiqarishi mumkin
mahalliy kod va boshqariladigan kod.
Integratsiyalashgan tuzatuvchi ham manba darajasida, ham mashina darajasida
tuzatuvchi sifatida ishlaydi. Boshqa o'rnatilgan vositalar a kod profiler, qurilish
uchun dizayner GUI ilovalar, veb-dizayner, sinf dizayner va ma'lumotlar bazasi
sxemasi dizayner. U deyarli har qanday darajada funksiyani
kengaytiradigan plaginlarni qabul qiladi, shu jumladan qo'llab-quvvatlashni
ham qo'shadi manbani boshqarish tizimlar (shunga o'xshash: Subversion va
Git ) uchun muharrirlar va vizual dizaynerlar kabi yangi vositalarni qo'shish
domenga xos tillar yoki boshqa jihatlari uchun asboblar to'plami dasturiy
ta'minotni ishlab chiqish davri. Vizual Studio 36 turini qo'llab-quvvatlaydi
dasturlash tillari va kod muharriri va disk raskadrovka dasturiga deyarli har
qanday dasturlash tilini (har xil darajada) qo'llab-quvvatlashga imkon
6

beradi, agar tilga xos xizmat mavjud bo'lsa. Ichki tillarga quyidagilar kiradi : C,
[8] C ++, C ++ / CLI, Visual Basic .NET, C #, F #,[9] JavaScript, TypeScript, XML,
XSLT, HTML va CSS. Kabi boshqa tillarni qo'llab-quvvatlash Python,[10]
Yoqut, Node.js va boshqalar qatorida mavjud plaginlari. Java (va J # ) o'tmishda
qo'llab quvvatlandi.
II BOB . MA’LUMOTLARNI QIDIRISH.
MA'LUMOTLARNI QIDIRISH
Kompyuterda ma'lumotlarni qayta ishlashda qidiruv asosiy amallardan biri
hisoblanadi. Uning vazifasi berilgan argument bo'yicha massiv ma'lumotlari
ichidan mazkur argumentga mos ma'lumotlarni topish yoki bunday ma'lumot
yo'qligini aniqlashdan iborat.
Ta'rif: Agar kalitlar ma’lumotlar jadvalidan ajratib olinib alohida fayl sifatida
saqlansa, u holda bunday kalitlar tashqi kalitlar deyiladi. Aks holda, ya'ni
yozuvning bir maydoni sifatida jadvalda saqlansa ichki kalit deyiladi.
Ma’lumotlarni qidirish algoritmlari bu – to’plam ma’lumotlar orasidan ma’lum
bir kalit so’zga mos keluvchi elementlarni qidirishga aytiladi. Hozirgi davrda
qidiruv algoritmlarisiz ishlaydigan IT tizimlar deyarli mavjud emas.
Ma’lumotlarni qidirish algoritmlari odatda ikki toifaga bo’linadi bular
quyidagilar:
Tarkibiy qidiruv: Bunda ro'yxat yoki qator ketma-ket o'tkaziladi va har bir
element tekshiriladi. Masalan, Chiziqli qidiruv.
Intervalli qidirish : Ushbu algoritmlar maxsus ajratilgan ma'lumotlar
tuzilmalarida qidirish uchun mo'ljallangan. Ushbu turdagi qidiruv
algoritmlari Linear Search ga qaraganda ancha samaralidir, chunki ular
7

qayta-qayta qidiruv tuzilmasi markaziga yo’naladi va qidiruv maydonini ikkiga
bo’ladi. Masalan, Binar qidiruv.
BINAR QIDIRUV.
Binar qidiruvning asosiy g'oyalaridan biri ketma-ket ikkiga bo'lishga asoslanadi,
ya'ni berilgan x ni massivning o'rtadagi elementi bilan solishtiradi, agar katta
bo'lsa oxiri va o'rtasi orasidagi massivni oladi, agar kichkina bo'lsa boshi va
o'rtasi orasidagi massivni oladi, va har safar shu jarayon takrorlanib boradi toki
x element solishtirilayotgan massivning elementga teng bo'lgunicha yoki
massivning elementlari qolmaguncha.
Chiziqli qidirish.
Chiziqli qidirish algoritmi juda oddiy algoritm bo'lib, u arraydagi har bir
elementni qidirilayotgan element bilan birma-bir solishtirib chiqadi. Algoritm
murakkabligi O(n) bo'lib, bu real hayotda juda ham sekin bo'lishi mumkin.
Tasavvur qilaylik Facebookning 1 mlrd foydalanuvchisi bor va foydalanuvchi o'z
profiliga kirmoqchi. Bunda Facebook foydalanuvchi loginini chiziqli qidirishdan
foydalanib tekshiradigan bo'lsa va bunda kompyuter sekundiga 10⁶ ta loginni
tekshirgan taqdirda ham, o'sha foydalanuvchi profiliga kirishi uchun 1000
soniya (16.6 daqiqa) kutishi kerak bo'lardi. Shu sababli ham bunday holatlar
uchun bizga samaraliroq algoritmlar kerak bo'ladi.
2.1.CHIZIQLI QIDIRISH VA IKKILIK QIDIRISH O'RTASIDAGI
FARQ.
Maʼlumotlar tuzilmasi va algoritmlarda ikkilik qidirish haqida
Ikkilik qidirish — Ο(log n) vaqti murakkabligi bilan tezkor qidiruv algoritmi.
Ushbu qidirish algoritmi boʻlinish (divide) va yengish (conque) prinsipi asosida
8

ishlaydi. Ushbu algoritm toʻgʻri ishlashi uchun maʼlumotlar toʻplanishi
tartiblangan shaklda boʻlishi kerak.
Ikkilik qidirish to’plamning ko’p qismini oʻrtasini taqqoslash orqali maʼlum bir
narsani qidiradi. Agar mos kelsa, unda element indeksi qaytariladi. Agar oʻrta
qism elementdan kattaroq boʻlsa, u holda ushbu element oʻrta qismning chap
tomonidagi pastki qatorda qidiriladi. Aks holda, element oʻrta elementning
pastki qismidagi pastki qatorda qidiriladi. Ushbu jarayon pastki massivda,
shuningdek sub massivning kattaligi nolga tushguncha davom etadi.
Ikkilik qidirish qanday ishlaydi?
Ikkilik qidirish ishlashi uchun maqsad qatorini tartiblash kerak. Ikkilik qidirish
jarayonini tasvirli misol yordamida bilib olamiz. Quyidagi tartiblangan
massivimiz boʻlib, ikkilik qidirishdan foydalanib, 31 qiymatni qidirish kerakligini
taxmin qilaylik.
Birinchidan, ushbu formuladan foydalanib, massivning yarmini aniqlaymiz:
mid = low + (high - low) / 2
Bu yerda, 0 + (9 - 0 ) / 2 = 4 (4.5 ning butun qiymati). Shunday qilib, 4 qatorning
oʻrtasida.
9

Endi biz 4-chi joyda saqlangan qiymatni, yaʼni qidirilayotgan qiymat bilan
taqqoslaymiz, yaʼni 31-chi joyda 27-ning qiymati mos kelmasligini aniqladik.
Qiymat 27 dan katta boʻlsa va bizda tartiblangan qator mavjud boʻlsa, biz shuni
ham bilamizki, maqsad qiymati massivning yuqori qismida boʻlishi kerak.
Biz pastligimizni + 1 oʻrtasiga oʻzgartiramiz va yana yangi oʻrtacha qiymatni
topamiz.
low = mid + 1
mid = low + (high - low) / 2
Bizning yangi o‘rtamiz endi 7 ga chiqdi. Biz 7-joyda saqlangan qiymatni
maqsadli qiymatimiz 31 bilan taqqoslaymiz.
7-joyda saqlangan qiymat mos kelmaydi, aksincha biz qidirayotgan narsadan
koʻproqdir. Shunday qilib, qiymat ushbu joyning pastki qismida boʻlishi kerak.
10

Shunday qilib, biz yana oʻrtani hisoblaymiz. Bu safar 5 ga .
Biz 5-chi joyda saqlangan qiymatni maqsadli qiymatimiz bilan taqqoslaymiz. Bu
match ekanligini aniqladik.
31 maqsadli qiymat 5 manzilda saqlanadi degan xulosaga keldik.
Ikkilik qidirish qidiriladigan qismlarni ikki baravar qisqartiradi va shu bilan juda
kam sonlar uchun taqqoslash sonini kamaytiradi.
Pseudocode
Ikkilik qidirish algoritmlarining kodi quyidagicha koʻrinishi kerak:
Procedure binary_search
A ← sorted array
n ← size of array
x ← value to be searched
Set lowerBound = 1
11

Set upperBound = n
while x not found
if upperBound < lowerBound
EXIT: x does not exists.

set midPoint = lowerBound + ( upperBound - lowerBound ) / 2

if A[midPoint] < x
set lowerBound = midPoint + 1

if A[midPoint] > x
set upperBound = midPoint - 1
if A[midPoint] = x
EXIT: x found at location midPoint
end while

end procedure
12

Chiziqli qidirish vs Ikkilik qidirish
Umumiy jihatlar :
Ikki algoritm uchun umumiy bo’lgan jihatlar, albatta, bu ularning qiladigan ishi
va beradigan natijasida. Ya’ni ikki algoritm ham arraydan qandaydir elementni
birorta shart asosida tekshiradi va element indeksini javob sifatida qaytaradi.
Bundan tashqari ikkala algoritmda ham ishlashi uchun qo’shimcha xotiradan
joy talab qilinmaydi, ya’ni ikki algoritmning hotira bo’yicha murakkabliki O(1)
ga teng.
Biz uchun esa hozir ularning farqli tomonlari muhimroq.
Algoritmlarning farqli tomonlari:
1.Kiruvchi ma’lumot
Bu ikki algoritmning asosiy farqi, oldingi darslarimizda ham ko’p marta
ta’kidlaganimizdek, ikkilik qidirish algoritmi ishlashi uchun array saralangan
bo’lishi shart. Chiziqli qidirish algoritmida esa bu narsaga hojat yo’q. Aynan shu
jihati bilan chiziqli qidirish algoritmi ikkilik qidirishdan ko’ra ustunlik qilishi
13

mumkin. Chunki ba’zi holatlarda ma’lumot saralanmagan bo’lishi va uni
saralash ko’proq vaqt olib qo’yishi mumkin.
2. Qidirish jarayoni
Chiziqili qidirish algoritmi elementni array boshidan tartib bilan qidiradi. Ikkilik
qidirish algoritmida esa bu jarayon array o’rtasidan boshlanib turlicha davom
etishi mumkin. Dasturlashda bu jarayon tasodifiy elementga murojaat (random
access) deb ataladi. Bu narsa qidirish algoritmi ish bajarayotgan ma’lumot
tuzilmasi uchun muhim. Chunki ba’zi tuzilmalarda tasodifiy elementga birdan
murojaat qilishning iloji yo’q. Masalan, stack, queue, linked list va h.k.
3. Solishtirish
Elementni qidirishda solishtirish jarayoni ham ikki xil bo’ladi. Chiziqli qidirish
algoritmi faqat tenglikka asoslanadi. Ikkilik qidirish esa tenglik, katta yoki
kichiklikka qarab, o’z ishini davom ettiradi.
4. Vaqt bo’yicha murakkablik
Ikkita bir xil vazifani bajaruvchi algoritmlarni solishtirayotgan paytda ularning
ishlash tezligini solishtirib ko’rmasdan iloj yo’q albatta.
Demak, Chiziqli qidirish ishlash tezligi:
1.Eng yaxshi holatda: O(1)
2.O’rtacha holatda: n(n+1)/2n = O(n)
3.Eng yomon holatda: O(n)
Ikkilik qidirish ishlash tezligi:
1.Eng yaxshi holatda: O(1)
2.O’rtacha holatda: logn(logn+1)/2logn = O(logn)
14

3.Eng yomon holatda: O(logn)
Shunday qilib yuqorida sanab o’tganlarimiz chiziqli qidirish va ikkilik qidirish
algoritmlari farqlari va umumiy jihatlari edi.
Lineer qidirish va ikkilik qidirish - bu massivlarda ishlatiladigan ikkita usul
qidirish elementlar. Qidirish - bu istalgan tartibda yoki tasodifiy saqlangan
elementlar ro'yxatidagi elementni topish jarayoni.
Chiziqli qidiruv va ikkilik qidirishning asosiy farqi shundaki, ikkilik qidirish
elementlarni saralangan ro'yxatidan qidirish uchun oz vaqt talab etadi.
Shunday qilib, ikkilik qidirish usulining samaradorligi chiziqli qidirishdan
kattaroq degan xulosaga kelish mumkin.
Ikkalasining yana bir farqi shundaki, ikkilik izlash uchun zarur shart mavjud,
ya'ni elementlar bo'lishi kerak saralangan chiziqli qidirishda esa bunday zarur
shart yo'q. Ikkala qidirish usullari ham quyida muhokama qilinadigan turli xil
usullardan foydalangan bo'lsa-da.
Lineer qidiruv ta'rifi.
Chiziqli qidiruvda massivning har bir elementi birma-bir mantiqiy tartibda
olinadi va kerakli element yoki yo'qligini tekshiradi. Agar barcha elementlarga
kirilsa va kerakli element topilmasa, qidiruv muvaffaqiyatsiz bo'ladi. Eng yomon
holatda, o'rtacha holatlar soni biz qatorning yarmini skanerlashimiz kerak (n /
2).
Shuning uchun chiziqli qidiruvni ushbu elementni topish uchun qatorni ketma-
ket bosib o'tadigan texnika deb ta'riflash mumkin. Quyida keltirilgan dastur
qidiruv yordamida massiv elementini qidirishni tasvirlaydi.
Chiziqli qidiruv samaradorligi.
15

Qidiruv jadvalidagi yozuvni qidirishda vaqt sarfi yoki taqqoslashlar soni
texnikaning samaradorligini belgilaydi. Agar kerakli yozuv qidiruv jadvalining
birinchi pozitsiyasida bo'lsa, unda faqat bitta taqqoslash amalga oshiriladi.
Kerakli yozuv oxirgi bo'lsa, n ta taqqoslash kerak.
Agar yozuv qidiruv jadvalida biron bir joyda ko'rsatilishi kerak bo'lsa, o'rtacha
taqqoslashlar soni (n + 1/2) bo'ladi. Ushbu texnikaning eng yomon
samaradorligi O (n) bajarilish tartibini anglatadi.
Ikkilik qidiruv ta'rifi.
Ikkilik qidirish juda samarali algoritmdir. Ushbu qidiruv texnikasi ushbu
elementni izlash uchun kamroq vaqt sarflaydi va mumkin bo'lgan
taqqoslashlarda. Ikkilik qidiruvni amalga oshirish uchun avval massiv
elementlarini saralashimiz kerak.
Ushbu texnikaning mantiqi quyida keltirilgan:
•Dastlab, massivning o'rta elementini toping.
•Massivning o'rta elementi qidirilayotgan element bilan taqqoslanadi.
Uchta holat paydo bo'lishi mumkin:
1.Agar element kerakli element bo'lsa, qidiruv muvaffaqiyatli bo'ladi.
2.Agar element kerakli elementdan kam bo'lsa, unda faqat qatorning birinchi
yarmini qidiring.
3.Agar u kerakli elementdan kattaroq bo'lsa, unda massivning ikkinchi yarmida
qidiring.
Qidiruv maydonida element topilguncha yoki tugamaguncha, xuddi shu
amallarni takrorlang. Ushbu algoritmda har safar qidiruv maydoni kamayadi.
Shuning uchun taqqoslashlar soni ko'pi bilan log (N + 1). Natijada, bu chiziqli
16

qidiruv bilan taqqoslaganda samarali algoritmdir, ammo ikkilik qidiruvni
bajarishdan oldin qatorni saralash kerak.
Binar qidirish algoritmi ishlash prinsipi.
Ikkilik qidirish algoritmining ishlashini tushunish uchun kompyuter bilan oʻyin
oʻynab koʻramiz.
Oʻyin sharti :
Kompyuter 1 va 100 oraligʻida ixtiyoriy natural son tanlaydi.
Oldimizda turgan vazifa shu sonni iloji boricha kam taxmin ishlatgan holda
topish.
Har bir taxmindan keyin kompyuter sizga sizning taxminingiz kompyuter
tanlagan sondan katta yoki kichikligini aytadi.
Agar sizning taxminingiz kompyuter tanlagan son bilan bir xil boʻlsa, oʻyin
tugaydi.
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
17

ta boʻlgan holatda, biz har qanday tahminni koʻpi bilan 7 ta qadamda
topishimiz mumkin boʻladi.
Dasturi :
#include <bits/stdc++.h>
using namespace std;
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
return -1;
}
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
int result = binarySearch(arr, 0, n - 1, x);
(result == -1)
18

? cout << "Element massivda mavjud emas"

: cout << "Element indeksda mavjud " << result
return 0;
}
2.2."BO'LIB TASHLA VA HUKMRONLIK QIL" PARADIGMASI.
“Bo’lib tashla va hukmronlik qil” nimani anglatadi. Dasturlashda, bo’lib tashla
va hukmronlik qil — bu algoritmik paradigma bo’lib, bu paradigmaning asosiy
g’oyasi algoritmik masalalarni bosh masalaga o’xshash kichik qismlarga bo’lib
tashlab, ularni rekursiv hal qilishdan iborat.
Bu paradigmada masala qismlarga bo’linganligi sababli, qism masalalar bosh
masalaga qaraganda kichikroq bo’lishi va bu bo’linish to’xtashi uchun asos
holat bo’lishi kerak.
Barcha turdagi bo’lib tashla va hukmronlik qil algoritmlari 3 ta bosqichdan
iborat bo’ladi:
Bo’lib tashlash bosqichi. Bunda bosh masala huddi shu masalaga o’xshash
kichikroq masalalarga bo’lib chiqiladi.
Hukmronlik bosqichi. Asos holatimizga mos kelib qolgan qism masalalar huddi
u kabi yechiladi.
Birlashtirish bosqichi. Bu bosqichda yechilgan kichik qism masalalar qaytib
birlashtirib chiqiladi va bu bosh masala yechimi bo’ladi.
Shu sababli, bo’lib tashla hukmronlik qil paradigmasini 3 ta jumla bilan eslab
qolish mumkin: bo’lib tashla, hukmronlik qil, birlashtir. Boshida tushunish
19

ozroq qiyin bo’lishi tabiiy, shuning uchun bu paradigma g’oyasini tasvirlab
berishga harakat qilamiz.
“Bo’lib tashla va hukmronlik qil” paradigmasi asosiy masalalari
Bu paradigma dasturlashning juda mashhur algoritmlari asosini tashkil qiladi:
 Ikkilik qidirish (Binary Search)
 Merge Sort
 Quick Sort
 Eng yaqin ikki nuqta (Closest two points)
 Strassen ko’paytirishi (Strassen multiplication)
 Karatsuba algoritmi (Karatsuba algorithm)
 Cooley-Tukey algoritmi (Cooley-Tukey Algorithm)
“Bo’lib tashla va hukmronlik qil” paradigmasi afzalliklari qiyin masalalarni
osonlik bilan yechishga imkon beradi.
Bu paradigmaga asoslangan algoritmlar oddiy yechimlardan ko’ra tezroq
ishlaydi. Masalan: oddiy saralash bo’lgan Bubble Sortning tezligi O(n²) bo’lsa,
MergeSortniki O(n*logn) bunday algoritmlarni parallel hisoblovchi
sistemalarda hech qanday o’zgarishsiz ishlatish mumkin.
Bunday algoritmlarni qo’llashda xotira keshidan unumli foydalanish mumkin.
Chunki masalalar bo’linish jarayonida shunday kichik qismlarga ajraladiki, ularni
keshni o’zida turib yechish mumkin bo’ladi.
Haqiqiy sonlar uchun bunday algoritmlar aniqroq ishlaydi, chunki qism
yechimlardagi haqiqiy sonlar ustidagi amallar aniqroq bajariladi (masalan,
ko’paytirish algoritmlarida).
“Bo’lib tashla va hukmronlik qil” paradigmasi kamchiliklari
bunday paradigma asosida ishlaydigan algoritmlar rekursiyadan foydalanadi va
20

bu narsa ularni ishlashini ma’lum miqdorga sekinlashtiradi. Buning ustiga kichik
bir xato yechimni cheksiz takrorlanishga tushirib qo’yishi mumkin.
Asos shartni tanlashda yo’l qo’yilgan xato barcha qism masalalarda xatolik va
ortiqcha xotira ishlatilishiga olib keladi.
C++ da qanday qilib ikkilik qidiruvni yaratish.
Ikkilik qidiruvni misol bilan qanday ishlashini ko'rib chiqaylik, quyida keltirilgan
misolda, 9-qatorda biz 10 ta elementdan iborat massiv massivini yaratdik va
12-qatorda foydalanuvchidan o'z katakchalarini klaviaturadan to'ldirishini
so'radik.
20-qatorda biz foydalanuvchidan kalitni kiritishni so'raymiz (uni massivda
topish kerak bo'ladi), so'ngra foydalanuvchi tomonidan kiritilgan kalit
mavjudligini ikkilik qidirish bilan qatorni tekshiramiz. Agar biz kalitni massivdan
topsak, u holda kalit joylashgan katakning indeksini chiqaramiz.
XULOSA.
Ko'rib turganimizdek, ikkilik qidirish chiziqli qidirishdan ko'ra samaralidir,
chunki har safar biz qolgan massivning yarmini qidirishimiz kerak.
Ikkilik qidirish algoritmi ishlashi uchun array saralangan bo’lishi shart. Chiziqli
qidirish algoritmida esa bu narsaga hojat yo’q. Aynan shu jihati bilan chiziqli
qidirish algoritmi ikkilik qidirishdan ko’ra ustunlik qilishi mumkin. Chunki ba’zi
holatlarda ma’lumot saralanmagan bo’lishi va uni saralash ko’proq vaqt olib
qo’yishi mumkin.
Vikipediyaga ko'ra, o'rash uchun: kompyuter fanida algoritmlarni kirish vaqti
kattalashgan sari ularning ishlash vaqti yoki makon talablariga qarab tasniflash
uchun katta O yozuvi ishlatiladi. Bu funktsiyalarni o'sish sur'atlariga ko'ra
21

tavsiflaydi. Shunday qilib, chiziqli qidirish uchun, massivning kattalashishi bilan
ishning eng murakkab holati O (n) bo'ladi.
Ikkala chiziqli va ikkilik qidirish algoritmlari dasturga qarab foydali bo'lishi
mumkin. Agar massiv ma'lumotlar tuzilishi bo'lsa va elementlar tartiblangan
tartibda joylashtirilsa, ikkilik qidiruvga ustunlik beriladi tezqidirish. Agar
bog'langan ro'yxat ma'lumotlar tuzilishi bo'lsa, elementlarning qanday
joylashtirilganligidan qat'i nazar, ikkilik qidiruv algoritmini to'g'ridan-to'g'ri
amalga oshirish mumkin emasligi sababli chiziqli qidirish qabul qilinadi.
Odatiy Ikkilik qidiruv algoritmini bog'langan ro'yxatga kiritish mumkin emas,
chunki bog'langan ro'yxat dinamik xarakterga ega va o'rta element aslida
qaerga berilganligi ma'lum emas. Shunday qilib, bog'langan ro'yxatda ishlashi
mumkin bo'lgan ikkilik qidiruv algoritmining o'zgarishini loyihalashtirish
talablari mavjud, chunki ikkilik qidiruv bajarilishida chiziqli qidiruvga qaraganda
tezroq.
Foydalanilgan adabiyotlar.
Cms.tuit.uz ma’ruza matnlari;
Internet saytlar;
sqlservertutorial.net;
jquery-az.com;
w3schools.com;
metanit.com;
Wikipediya.com;
Texnoman.uz;
22

Ikkilik qidirish (Binary search) C#

Купить