logo
  1. Главная страница
  2. Дипломные работы
  3. Общий
  4. Butun sonli ikkilik qidiruv algoritmi

Butun sonli ikkilik qidiruv algoritmi

Загружено в:

12.08.2023

Скачано:

0

Размер:

103.671875 KB
Скачать
Mavzu:”Butun sonli ikkilik qidiruv algoritmi” MUNDARIJA KIRISH…………………………………………..3 I Bob. Butun sonli ikkilik qidiruvni nazariy asoslari. 1.1.Butun sonli ikkilik qidiruv haqida…………..4 1.2.Algoritm tushunchasi………………………….6 1.3. Muvaffaqiyatli qidiruvlar……………………..7 1.4. Muvaffaqiyatsiz qidiruvlar…………………… 11 II Bob.Butun sonli ikkilik qidiruvni ishlab chiqish..12 2.1. Shovqinli ikkilik qidiruv …………………….12 2.2.Kvant ikkilik qidiruv…………………………..12 2.3. Muqobil protseduraning bajarish……………..15 2.4. Lineer qidiruv………………………………..16 Xulosa…………………………………………..19 ADABIYOTLAR RO’YXATI………………….20 KIRISH Butun sonli ikkilik qidiruv algoritmi . “Dasturlashning eng asosiy muommosi - bu murakkablik . Murakkablik ni hal qilishning faqatgina bitta asosiy yo’li bor : Bo’lib tashla va hukmronlik qil “ -- Bjarni Stroustrup 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 3ta bosqichdan iborat bo’ladi : 1.Bo’lib tashlash bosqichi . Bunda bosh masala huddi shu masalaga o’xshash kichikroq masalalarga bo’lib chiqiladi . 2.Hukmronlik bosqichi . Asos holatimizga mos kelib qolgan qism masalalar huddi u kabi yechiladi . 3.Birlashtirish bosqichi. Bu bosqichda yechiladigan kichik qism masalalar qaytib birlashtirish chiqiladi va bu bosh masala yechimi bo’ladi . I.Bob. Butun sonli ikilik qidiruvni nazariy asoslari . 1.1. Butun sonli ikkilik qidiruv haqida . Algoritm fanida ikkilik qidiruv , shuningdek , yarim intervalli qidiruv ,logarifmik qidiruv yoki ikkilik chop deb nomlanuvchi , tartiblangan massiv ichida maqsadli qiymatning o’rnini topadigan qidiruv algoritmidir. Ikkilik qidiruv maqsadli qiymatni massivning o’rta elementi bilan solishtiradi . Agar ular teng bolmasa , nishon yo’qolmaydigan yarmi yo’q qilinadi. Va qolgan yarmida qidirish yana davom etadi. Maqsadli qiymat bilan solishtirish uchun o’rta elementi olish va maqsadli qiymat topilguncha buni takrorlash. Agar qidiruv qolgan yarmi bo’sh bo’lishi bilan tugasa , maqsad massivda emas. Ikkilik qidiruv algoritmi. Ikkilik qidiruv algoritmining vizualizatsiyasi. 7 maqsadli qiymatlari Class qidiruv algoritmi Malumotlar tuzilishi massiv Eng yomon ishlash O(log n) Eng yaxshi holat O(1) O’rtacha ishlash O(log n) Eng yomon holatda bo’sh joy Q(1) Ikkilik qidiruv eng yomon holatda logarifmik vaqtda ishlaydi, O(logn) taqqoslashlarni amalga oshiradi, bu yerda n massivdagi elementlari soni. Ikkilik qidiruv kichik massivlardan tashqari chiziqli qidiruvga qaraganda tezroq. Biroq, ikkilik qidiruvni qo’llash uchun massiv avval tartiblangan bo’lishi kerak. Tez qidirish uchun mo’ljallangan maxsus ma’lumotlar tuzilmalari mavjud , masalan , xesh-jadvallar, ularni ikkilik qidiruvdan ko’ra samaraliroq qidirish mumkin. Biroq , ikkilik qidiruv kengroq muommolarni hal qilish uchun ishlatilishi mumkin, masalan, massivda yo’q bo’lsa ham, maqsadga nisbatan massivdagi keyingi eng kichik yoki keyin eng katta elementni topish. Ikkilik qidiruvning ko’plab variantlari mavjud. Xususan , Kasrli kaskad bir nechta massivlarda bir xil qiymat uchun ikkilik qidiruvni tezlashtiradi . Fraksional kaskad hisoblash geometriyasida va boshqa ko’plab sohalarda bir qator qidiruv muommolarini samarali hal qiladi. Eksponensial qidiruv ikkilik qidiruv cheklanmagan ro’yxatlargacha kengaytiradi . Ikkilik qidiruv daraxt va B-daraxt ma’lumotlar tuzilmalari ikkilik qidiruvga asoslangan. 1.2. Algoritm tushunchasi. Ikkilik qidiruv tartiblangan massivlarda ishlaydi. Ikkilik qidiruvga massivning o’rtasida joylashgan elementlarni bilan solishtirishdan boshlanadi. Agar maqsadli elementga mos kelsa, uning massivdagi o’rni qaytariladi. Agar maqsadli qiymat elementdan kichik bo’lsa, qidiruv massivning pastki yarmida davom etadi. Shunday qilib, algoritm har bir iteratsiyada maqsadli qiymat yotmasligi mumkin bo’lgan yarmini yo’q qiladi. Protecure - jarayon A 0, A 1 ,A 2,: ……………A n-1 qiymatlari yoki yozuvlari bo’lgan n ta elementdan iborat A massivi shunday tartiblanganki, A 0 < A 1 < A 2 <……………..< A n-1 va maqsad qiymat T bo’lsa quyidagi dastur Adagi T indekisini topish uchun ikiklik qidiruvdan foydalaniladi. Function binary_search(A, n, T) is L :=0 R :=n-1 While L<R do, m := floor(L+R)/2 if A(m)< T then L : = m + 1 else if A(m) > T then R : = m - 1 else : return m return unsuccessful Shu bilan bir qatorda , algoritm L+R/2 shiftini olish mumkin. 1.3.Muvaffaqiyatli qidiruvlar . Butun sonli ikkilik qidiruv daraxti ko’rinishda muvaffaqiyatli qidirish ichki yo’l deb ataladigan ildizdan maqsadli tugungacha bo’lgan yo’l bilan ifodalanishi mumkin. Butun sonli ikkilik qidiruv solishtirishlar yordamida qidirish uchun optimal algoritm bo’lganligi sababli, bu muommo n ta tugunli barcha binar daraxtlarning minimal ichki yo’l uzunligi hisoblash uchun qisqartiriladi, bu quyidagilarga teng: I(n) = ∑ k=1 n (log 2 (k)) Masalan, 7 element massivda ildiz bir iteratsiyani talab qiladi, ildiz ostidagi ikkita element ikkita takrorlashni va quyidagi joylashgan to’rtta elementni talab qiladi. Muqobil protsedura Yuqoridagi protsedurada algoritm har bir iteratsiyada o’rta element (m) maqsad (T) ga teng yoki yo’qligini tekshiradi. Ba’zi ilovalar har bir iteratsiya paytida ushbu tekshiruvni o’tkazib yuboradi. Algoritm bu tekshirishni faqat bitta element qolganda (L=R bo’lganda ) amalga oshiradi. Bu tezroq taqqqoslash davriga olib keladi, chunki har biriga bitta taqqoslash o’chiriladi. Hermann Bottenbruch 1962-yilda ushbu tekshiruvni o’tkazib birinchi dasturni nashr etdi. L ni 0 va R n-1 L ga teng emas R 1. m ni (o’rta elementning joylashuvi ) L+R/2 ni o’rnating , kichik butun son L+R/2 dan katta. 2. Agar A m > T, bo’lsa, R ni m-1 ga qo’ying . 3. Aks holda , A m < T; L ni m ga qo’ying. 4. Endi L=R qidiruv amalga oshiriladi. Agar A L = T , bo’lsa L ni qaytaring. Aks holda , qidiruv muvaffaqiyatsiz tugaydi. Shift ceil funksiyasi bo’lsa, ushbu versiyaning psevdokodi: Funksiya binary _search _alternative( A, n, T) L : = 0 R : = n – 1 While L ! = R M : = ceil ((L+R)/2) If A(m) > T then R : = m – 1 else : L : = m If A(L) = T then return L return unsuccessful Takroriy elementlar . Protsedura, massivda takroriy elementlar mavjud bo’lsa ham, elementi maqsadli qiymatga teng bo’lgan har qanday indeksni qaytarishi mumkin. Misol uchun , Qidiriladigan massiv[ 1 , 2 , 3 , 4 , 5 , 6 , 7 ] va maqsad edi. Agar 4 bo’lsa , algoritm uchun to’rtinchi (indeks 3 ) ni qaytarish to’g’ri bo’ladi, yoki beshinchi (indeks 4) element . Oddiy protsedura bu holda 4-elementni (indeks 3) qaytaradi. U har doim ham birinchi dublikatni qaytarmaydi (hali 4-elementni qaytaradigan [ 1, 2 ,3 ,4 , 5 , 6 , 7] ni ko’rib chiqing ). Biroq, ba’zan massivda takrorlanadigan maqsadli qiymat uchun eng chap elementni yoki eng o’ng elementni topish kerak bo’ladi. Yuqoridagi misolda 4 - element 4 – qiymatning eng chap elementi, 5 – element esa 4 - qiymatning eng o’ng elementidir. Yuqoridagi muqobil protsedura, agar shunday element mavjud bo’lsa , har doim eng o’ngdagi element indeksini qaytaradi. Eng chap elementni topish tartibi. Eng chap elementni topish uchun quyidagi protseduradan foydalanish mumkin: 1. L ni 0 ga va R ni n ga o’rnating. 2. L<R bo’lsa , 1. L+R/2 ning qavatga m (o’rta elementning o’rni) qo’ying. 2. A m <T , ga teng bo’lgan butun sondir. 3. Aks holda , A m >T; R ni m ga o’rnating. Qayerda floor funksiyasi bo’lsa, Ushbu dastur psevdokodi: funksiya binary_search_leftmost ( A , n , T ): L : = 0 R : = n While L < R : m : =floor (L+R)/2) if A(m) < T : L : = m + 1 E else : R : = m return L O’ng elementni topish tartibi. Butun sonli ikkilik qidiruvni taxminiy mosliklarni bajarish uchun kengaytirish ahamiyatsiz, chunki ikkilik qidiruv tartiblangan massivlarda ishlaydi. Masalan , ikkkilik qidiruv ma’lum bir qiymat uchun uning darajasi (kichikroq elementlar soni ), oldingi (keyingi - eng kichik elementlar ), vorisi (keyingi - eng katta element ) va eng yaqin qo’shnisini hisoblash uchun ishlatilishi mumkin . 50 30 20 40 90 80 100 Ikkilik qidiruvni ifodalovchi daraxt. Bu yerda [20 , 30, 40, 50, 80, 90, 100] va har biri qidirilmoqda.Qiymat 40 ekan. Kosmik murakkablik. Butun sonli ikkilik qidiruv uchun elementlarga uchta ko’rsatgich kerak bo’ladi , ular massiv indekslari yoki xotira joylariga ko’rsatgich bo’lishi mumkin. Shuning uchun butun sonli ikkilik qidiruvning murakkabligi hisoblashning so’zli RAM modelida O(1) dir. Iteratsiya , o’rtacha va eng yomon holatda talab qilinadigan takrorlash sonini oshirish . Bu taqqoslashga asoslangan boshqa qidiruv algoritmlari uchun ham shundaydir , chunki ular ba’zi maqsadli qiymatlarda tezroq ishlashi mumkin bo’lsa-da, barcha elementlar bo’yicha o’rtacha qidiruvga qaraganda yomonroqdir . Massivni ikkiga bo’lish orqali ikkilik qidiruv ikkala pastki massivning ishlash ikkilik o’lchamlari o’xshash bo’lishini ta’minlaydi . imkon qadar O’rtacha ishning chiqarilishi . Butun sonli ikkilik qidiruv orqali amalga oshiriladigan iteratsiyalarning o’rtacha soni har bir elementning izlanish ehtimoliga bog’liq . Muvaffaqiyatli qidiruvlar va muvaffaqiyatsiz qidiruvlar uchun o’rtacha holat boshqacha. Muvaffaqiyatli qidiruvlar uchun har bir element bir xil darajada qidiriladi deb taxmin qilinadi . Muvaffaqiyatsiz qidiruvlar uchun intervallar deb taxmin qilinadi. Muvaffaqiyatli qidiruvlar uchun o’rtacha holat har bir elementni bir marta izlash uchun zarur bo’lgan takrorlashlar soni bo’lib n ga bo’linadi , elementlar soni. Muvaffaqiyatsiz qidiruvlar uchun o’rtacha holat har bir oraliqda bir elementni bir martadan izlash uchun zarur bo’lgan takrorlashlar soni bo’lib, n + 1 oraliqda bo’linadi . 1.4.Muvaffaqiyatsiz qidiruvlar . Muvaffaqiyatsiz qidiruvlar daraxtni kengaytirilgan ikkilik daraxtni tashkil etuvchi tashqi tugunlar bilan ko’paytirish orqali ifodalanishi mumkin . Agar ichki tugun yoki daraxtda mavjud bo’lgan tugun ikkitadan kam bo’lmagan tugunga ega bo’lsa , har bir ichki tugun ikkitadan bo’lakga ega bo’lishi uchun tashqi tugunlar deb nomlanuvchi qo’shimcha tugunlar qo’shiladi . Shunday qilib , qidirish muvaffaqiyatsiz bo’lishi mumkin . Ota - onasi oxirgi iteratsiya davomida qolgan yagona element bo’lgan tashqi tugunga yo’l - bu ildizdan tashqi tugungacha bo’lgan yo’l . Tashqi yo’l uzunligi barcha noyob tashqi yo’llarning uzunliklarning yig’indisidir. Agar musbat butun son bo’lgan n ta element bo’lsa va tashqi yo’l uzunligi E( n ) bo’lsa , u holda iteratsiyaning o’rtacha soni muvaffaqiyatsiz qidiruv T’( n ) = E( n ) / n – 1 , hisoblash uchun bir iteratsiya qo’shilgan n + 1 ‘ . Tashqi yo’l uzunligi n o’rniga n +1 ga bo’linadi , chunki n + 1 tashqi yo’llar mavjud, massiv elementlari orasidagi va tashqaridagi intervallarni ifodalaydi . Ushbu muommoni xuddi shunday n tugunli barcha ikkilik daraxtlarning minimal tashqi yo’l uzunligi ichki yo’l uzunligi + 2 n ga tengdir. II Bob. Butun sonli ikkilik qidiruvni ishlab chiqish. 2.1.Shovqinli ikkilik qidiruv . Shovqinli ikkilik qidiruv algoritmlari algoritm massiv elementlarini ishonchli taqqoslay olmaydigan holatlarni hal qiladi . Har bir juft element uchun algoritm natog’ri taqqoslash ehtimoli bor . Shovqinli ikkilik qidiruv maqsadning to’g’ri o’rnini topishi mumkin daramodli pozitsiyaning ishonchliligini nazorat qiliuvchi berilgan ehtimollik bilan . Har bir shovqinli ikkilik qidiruv protsedurasi kamida amalga oshirilishi kerak 2.2. Kvant ikkilik qidiruv. Klassik kompyuterlar ikkkilik qidiruvni amalga oshirishda aniq [ log 2 n + 1 ] iteratsiyalarning eng yomon holati bilan chegaralanadi . Ikkilik qidiruv uchun kvant algoritmlari hali ham log2 n so’rovlar nisbati bilan chegaralangan ( klassik protseduraning takrorlanishini ifodalaydi ) , lekin doimiy omil bittadan kamroq bo’lib , kvant kompyuterlarida kamroq vaqt murakkabligini ta’minlaydi . Har qanday aniq kvant ikkilik qidiruv protsedurasi , ya’ni har doim to’g’ri natija beradigan protsedura hech bo’lmaganda talab qiladi . Tarix. Tezroq qidirish imkonini beradigan narsalar ro’yxatini saralash g’oyasini antik davrga borib taqaladi . Ma’lum bo’lgan eng qadimgi misol Bobildan eramizgacha bo’lgan Inakibit – Anu planshetidir . Miloddan avvalgi 200 yil . Planshetda 500 ga yaqin sexagesimal mavjud raqamlar va ularning o’zaro leksikografik tartibda tartiblangan , bu ma’lum bir yozuvni qidirishni osonlashtiradi . Bundan tashqari , Egay orollarida birinchi harfi bo’yicha saralangan bir nechta nomlar ro’yxati topilgan . Milodiy 1286 - yilda tugallangan lotincha lug’at katolikon so’zlarni faqat birinchi harflardan farqli ravishda alifbo tartibda tartiblash qoidalarini tavsiflovchi birinchi asar edi . 1946 – yilda Jon Mauchli birinchi bo’lib hisoblash bo’yicha kollejning asosiy va asosiy kursi bo’lgan Mur maktabi ma’ruzalarining bir qismi sifatida ikkilik qidiruv haqida gapirdi . 1957 - yilda Uilyam Uesli Peterson interpolatsiyani qidirishning birinchi usulini nashr etdi . Har bir nashr etilgan ikkilik qidiruv algoritmi 1960 yilgacha Derrik Genri Lehmer barcha massivlarda ishlaydigan ikkilik qidiruv algoritmini nashr etgunga qadar uzunligi ikkilik kuchidan bir kichik bo’lgan massivlar uchungina ishlagan . 1962 – yilda Hermann Bottenbruch ikkilik qidiruvning ALGOL 60 dasturini taqdim etdi , u oxirida tenglik uchun taqqoslashni joylashtirdi , o’rtacha takrorlash sonini bittaga oshirdi , lekin har bir iteratsiya uchun taqqoslash sonini bittaga qisqaradi . Yagona ikkilik qidiruv 1971 – yilda Stenfod universitetidan A .K.Chandra tomonidan ishlab chiqilgan . 1986 - yilda Bernard CHazelle va Leonids J. Guibas hisolash geometriyasini ko’plab qidiruv nuommmolarini hal qilish usuli sifatida kasr kaskadlarini kiritdilar . Amalga oshirish masalari . Ikkilik qidiruvning asosiy g’oyasi nisbatan sodda bo’lsa – da , tafsilotlar hayratlanarli darajada qiyin bo’lishi mumkin . ______Donald Knut. Jon Bentley , uchun kursda muommo sifatida ikkilik qidiruv tayinlangan professional dasturchilar , u to’qson foizi bir neha soat ishlaydigan so’ng to’g’ri yechimni ta’minlay olmaganini aniqladi , chunki bu notog’ri ilovalar 13 ishlamay qolgan yoki kamdan – kam holllarda nato’g’ri javob. 1988 – yilda nashr etilgan tadqiqot shuni ko’rsatdiki , uning aniq kodi faqat yigirmata darslikdan beshtasini topilan . Bundan tashqari , Bentley o’zining 1986 – yilda chop etilgan “Programming Pearls” kitobida chop etilgan ikkilik qidiruvni amalga oshirishda yigirma yildan ortiq vaqt davomida aniqlanmagan to’lib – toshgan xatolikni o’z ichiga olgan . Java dasturlash tili kutubxonasi ikkilik qidiruvni amalga oshirishga ega edi . Amalga oshirishda indekslarni ifodalash uchun ishlatiladigan o’zgaruvchilar ko’pincha qat’iy o’lchamda ( butun sonlar ) bo’ladi va bu juda katta massivlar uchun arifmetik to’lib ketishiga olib kelishi mumkin . Agar L + R ning o’rta nuqtasi oraliq sifatida hisoblanadi L + R /2, keyin L + R qiymati , hatto L va R diapazonda bo’lsa ham , o’rta nuqtani saqlash uchun ishatiladigan ma’umotlar turining butun sonlari oralig’idan oshib ketishi mumkin . Agar L va kamdan – kam hollarda manfiy emas , bu o’rta nuqtani L + R - L /2 sifatida hisoblash orqali oldini olish mumkin . Loop uchun chiqish shartlari to’g’ri aniqlanmagan bo’lsa , cheksiz sikl paydo bo’lishi mumkin . L R dan oshib ketganda , qidiruv muvaffaqiyatsiz tugaydi va qidiruvning muvaffaqiyatsizligini bildirishi kerak . Bunga qo’shimcha ravishda , maqsad element topilganda sikldan chiqish kerak yoki bu chek oxirgacha ko’chirilganda , qidiruv oxirida muvaffaqiyatli yoki muvaffaqiyatsiz bo’lganligi tekshirdi . Bentley ikkilik qidiruvni nato’g’ri amalga oshirgan dasturchilarning ko’pchiligi chiqish shartlarini belgilashda xatoga yo’l qo’yganligini anqladi . Kutubxonani qo’llab – quvvatlash . Ko’pgina tillarning standart kutubxonalari ikkilik qidiruv tartiblarini o’z ichiga oladi . С bsearch( ) funksiyasini ta’minlaydi. Uning standart kutubxonasida , odatda ikkilik qidiruv orqali amalga oshiriladi, lekin rasmiy standart buni talab qilmasa ham . 14 C ++ ning standart andozalar kutubxonasi funksiyasalarini taqdim etadi. D standart kutubxonasi Phobos , std.range modulida turni taqdim etadi. 2.3. Muqobil protsedurani bajarish. Yuqoridagi tavsiflangan butun sonli ikkilik qidiruv protsedurasining har bir iteratsiyasi bir yoki ikkita taqqoslashni amalga oshiradi. O’rta element har bir iteratsiyada nishonga teng yoki yo’qligini tekshiradi. Har bir elementning izlanish ehtimoli bir xil bo’lsa har bir iteratsiya o’rtacha 1,5 ta taqqoslashni amalga oshiradi. Algoritmning o’zgarishi qidiruv oxiridagi o’rta elementning maqsadga teng yoki binary_sear ch( ) , lower_boun d( ) , upper_boun d( ), equal_rang e( ), yo’qligini tekshiradi. O’rtacha , bu har bir iteratsiyadan yarim taqqoslashni yo’q qiladi. Biroq, bu qidiruv maksimal takrorlanishlar sonini olishni kafolatlaydi, o’rtacha qidiruvga bir iteratsiya qo’shadi . Ishlash vaqtni keshdan foydalanish . Butun sonli ikkilik qidiruvning ishlashini tahlil qilishda yana bir e’tibor - ikkita elementni solishtirish uchun zarur bo’lgan vaqt . Uchun butun sonlar va satrlar , elementlarning kodlash uzunligi (odatda bitlar soni ) ortishi bilan talab qilinadigan vaqt chiziqli ravishda oshadi . Misol uchun , 64 – bitli belgisiz butun sonlarni solishtirish , 32 – bitli butun sonlarni solishtirish kabi bitlarni ikki baraborgacha solishtirishni talab qiladi . Eng yomon holatga butun sonlar teng bo’lganda erishiladi . Bu elementlarning kodlash uzunligi katta bo’lsa masalan , katta tamsayllar turlari yoki uzun satrlar bilan ahamiyatli bo’lishi mumkin. Bu esa elementlarni solishtirishni qimmat qiladi . Ko’pgina kompyuterlarda iteratsiyaga ketadigan vaqtni biroz qisqartiradi. Biroq, bu qidiruv maksimal takrorlanishlar sonini olishini kafolatlaydi. O’rtacha qidiruvga bir iteratsiya qo’shadi . Ikkilik qidiruv boshqa sxemalarga nisbatan.Ikkilik qidiruv bilan tartiblangan massivlar kiritishda juda samarasiz yechim hisoblandi. O’chirish operatsiyalari qidirish bilan aralashib , har bir bunday operatsiya uchun O( n ) vaqtni oladi . Bundan tashqari , tartiblangan massivlar xotiradan foydalanishni qiyinlashtirishi mumkin . Ayniqsa elementlar massiviga tez – tez kirilganda . Samaraliroq kiritish va o’chirishni qo’llab - quvvatlaydigan boshqa ma’lumotlar tuzulmalari ham mavjud . Ikkilik qidiruvdan aniq moslikni amala oshirish va a’zolikni o’rnatish uchun foydalanish mumkin . Tezroq aniq moslashish va a’zolikni sozlashni qo’llab – quvvatlaydigan ma’lumotlar tuzilmalari mavjud . Biroq , boshqa ko’plab qidiruv sxemalaridan farqli o’laroq , ikkilik qidiruv samarali taxminiy moslashish uchun ishlatilishi mumkin. 2.4.Linear qidiruv . Chiziqli qidiruv - bu maqsadli qiymatni topgunga qadar har bir yozuvni tekshiradigan oddiy qidiruv algoritmi . Chiziqli qidiruv bog’langan ro’yxatda amalga oshirishi mumkin, bu massivga qaraganda tezroq kiritish va o’chirish imkonini beradi . Ikkilik qidiruv tartiblangan massivlarni chiziqli qidirishdan tezroq massiv qisqa , massivni oldindan saralash kerak . Tezkor saralash va birlashtirish kabi elementlarni taqqoslashga asoslangan barcha tartiblangan algoritmlari eng yomon holatda kamida O( n log n ) taqqoslashni talab qiladi . Chiziqli qidiruvdan farqli o’laroq , ikkilik qidiruv samarali taxminiy moslashish uchun ishlatilishi mumkin . 8 3 1 6 4 6 4 7 10 14 13 --Ikklik qidiruv daraxti bu B-daraxt qidiruvga o’xshash algoritm qidiriladi. Ikkilik qidiruv daraxtlari strukturaviy qidiruvga o’xshash algoritm yordamida qidiriladi.Butun sonli ikkilik qidiruv daraxti ikkilik printsipi asosida ishlaydigan ikkilik daraxt ma’lumotlar strukturasidir . Daraxtning yozuvlari tartiblangan tartibda joylashtirilgan va daraxtdagi har bir yozuvni ikkilik qidiruvga o’xshash algoritm yordamida o’rtacha logarifmik vaqtni hisobga olgan holda qidirish mumkin . Qo’shish va o’chirish ikkilik qidiruv daraxtlarda o’rtacha logarifmik vaqtni ham talab qiladi . Bu tartiblangan massivlarning chiziqli vaqtini kiritish va o’chirishdan tezroq bo’lishi mumkin va binar daraxtlar tartiblangan massivda mumkin bo’lgan barcha operatsiyalarni , shu jumladan diapason va taxminiy so’rovlarni bajarish qobilyatidir . Biroq , ikkilik qidirish odatda qidiruv uchun samaraliroq bo’ladi , chunki ikkilik qidiruv daraxtlarni natog’ri muvozanatlashgan bo’lishi mumkin , bu ikkilik qidiruvga qaraganda biroz yomonroq ishlashga olib keladi . Bu hatto muvozanatli ikkilik qidiruv daraxtlari , o’z tugunlarini muvozanatlashtiradigan ikkilik qidiruv daraxtlari uchun ham amal qiladi, chunki ular kamdan - kam hollarda eng kam darajali daraxt hosil bo’ladi . Butun sonli ikkilik qidiruv tashqari , daraxt ikki bolali bir nechta daraxtlaridan ichki tugunlar bilan jiddiy nomutanosib bo’lishi mumkin, natijada o’rtacha va n taqqoslashga yaqinlashayotgan eng yomon holatda qidiruv vaqti, ikkilik qidiruv daraxrlari tartiblangan massivlarga qaraganda ko’proq joy egallaydi. Ikkilik qidiruv daraxtlari qattiq disklarda saqlanadigan tashqi xotirada tezkor qidiruvga yordam beradi , chunki ikkilik qidiruv daraxtlari fayl tizimlarida samarali tarzda tuzilishi mumkin. B – daraxt daraxtni tashkil qilishning ushbu usulini Umumlashtiradi . B – daraxtlar ko’pincha ma’lumotlar bazalari va fayl tizimlari kabi uzoq muddatli saqlashni tashkil qilish uchun ishlatiladi . Bo’lib tashla va hukmronlik qil paradigmasi asosiy masalalari . Bu paradigmada dasturlashning juda mashhur algoritmlari asosini tashkil qiladi: 1.Ikkilik qidiruv (Binary search) 2.Merga Sort 3.Quick Sort 4.Eng yaqin ikki nuqta (Closest two points ) 5.Strassen ko’paytirishni (Strassen multiplication ) 6.Karatsuba algoritmi (Karatsuba algorithm) 7.Cooley – Tukey algoritmi (Cooley – Tukey Algorithm ). Xeshlash. Assotsiativ massivlarni , xesh – jadvallarni , xaritalarni tuzadigan ma’lumotlar strukturasini amalga oshirish uchun Xesh funksiyasidan foydalangan holda yozuvlar uchun kalitlar odatda tartiblangan yozuvlar uchun kalitlar odatda tartiblangan yozuvlar massivda ikkilik qidiruvga qaraganda tezroq. Ko’pgina xesh – jadval ilovalari o’rtacha amortizatsiya qilingan doimiy vaqtni talab qiladi. Biroq , xeshlash keyingi eng kichik , va eng katta va eng yaqin kalitni hisoblash kabi taxminiy moslashuvlar uchun foydali emas, chunki muvaffaquyatsiz qidiruvda berilgan yagona ma’lumotlar maqsad hech qanday yozuvda mavjud emasligidir . Butun sonli ikkilik qidiruv logarifmik vaqtda bajariladigan bunday mosliklar uchun ideal. Ikkilik qidiruv ham taxminiy mosliklarni qo’llab – quvvatlaydi . Ba’zi operatsiyalar , masalan , eng kichik va eng kattasini topish elementini tartiblangan massivlarda samarali bajarish mumkin, lekin xesh jadvallarda emas. A’zolik algoritmlarini o’rnatish . Qidiruv bilan bog’liq muomo - bu a’zolik . Ikkilik qidiruv kabi qidiruv kabi qidiruvni amalga oshiradigan har qanday algoritm to’plamga a’zolik uchun ham ishlatilishi mumkin . To’plamga a’zolik uchun ko’proq mos keladigan boshqa algoritmlar mavjud . Bit massivi eng oddiy , kalitlar diapazoni cheklangan bo’lsa foydalidir. U bitlar to’plamini ixcham saqlaydi , har bir bit kalitlar oralig’ida bitta kalitni ifodalaydi . Bit massivlari juda tez, faqat O(1) vaqtni talab qiladi . Judy massivni 64 – bitli kalitlarni samarali boshqaradi . Taxminiy natijalar uchun Bloom filtlari, xeshga asoslangan boshqa ehtimolli ma’lumotlar srukturasi , bit qatori va bir nechta xesh funksiyasi yordamida kalitlarni kodlash orqali kalitlar to’plamini saqlaydi. Bloom filtrlari ko’p hollarda bit massivlariga qaraganda ancha tejamkor va sekinroq emas : hesh funksiyalar bilan a’zolik so’rovlari faqat O(K) vaqtni talab qiladi . Biroq , bloom filtrlari notog’ri musbatlardan aziyat chekmoqda . Ba’zi hollarda qidiruv va tartiblangan massivlar uchun mavjud bo’lgan boshqa operatsiyalar uchun ikkilik qidiruvni yaxshilash mumkin bo’lgan ma’lumotlar tuzilmalari mavjud . Masalan , saralangan massivlar uchun mavjud qidiruvlar , taxminiy mosliklar va operatsiyalari va Emde Boas daraxtlari , termoyadroviy daraxtlar , urinishlar va bit massivlari kabi maxsus ma’lumotlar tuzilmalarida ikkilik qidiruvga qaraganda samaraliroq bajaralishi mumkin . Ushbu maxsus ma’lumotlar tuzilmalari odatda tezroq bo’ladi , chunki ular ma’lum bir atributga ega bo’lgan kalitlarning xususiyatlaridan foydalaniladi( odatda kichik butun sonlar bo’lgan kalitlar) va shuning uchun bu atributga ega bo’lmagan kalitlar uchun vaqt yoki joy talab qilinadi . Yagona ikkilik qidiruv Middle element b=3 b=3 1 2 3 4 5 6 7 8 9 Yagona ikkilik qidiruv joriy va keyingi ikkita mumkin bo’lgan o’rta elementlar o’tasidagi farqni saqlaydi . Yagona ikkilik qidiruv pastki va yuqori chegaralar o’rniga joriy iteratsiyadan keyingi indeksni farqini saqlaydi. Farqlarni o’z ichiga olgan agar izlananadigan massiv [1 , 2 ,3 , 4 , 5 , 6 , 7 ,8 ,9 10 , 11 ] bo’lsa , o’rta element ( m ) 6 bo’ladi . Bu holda , o’rta chap pastki qatorning elementi ([1 , 2, 3 , 4 , 5 ]) 3 va o’ng pastki qatorning o’rta elementi ([7 , 8 , 9 , 10 , 11 ]) 9 . Yagona ikkilik qidiruvi 3 qiymati , chunki ikkala indeks ham 6 dan bir xil miqdorda farq qiladi . Qidiruv maydonini qisqartirish uchun algoritm qo’shadi yoki ayiradi , o’rta element ineksidan bu o’zgarish . Yagona ikkilik qidiruv o’rta nuqtani hisoblash samarasiz bo’lgan tizimlarda , masalan , kasrlarni kompyuterlarda tezroq bo’lishi mumkin. Eksponensial qidiruv. Eksponensial qidiruv ikkilik qidiruvni cheklanmagan ro’yxatlargacha kengaytiradi . U ikkining kuchi va elementni topishdan boshlanadi . Shundan so’ng , u o’rnatiladi bu indeks yuqori chegara sifatida va ikkilik qidiruvga o’tadi . Qidiruv ikkilik qidiruv boshlanishdan oldin [log 2 + 1 ] iteratsiyani va ikkilik qidiruvning ko’pi bilan [ log ] iteratsiyani oladi , bunda x maqsadli qiymatning o’rni . Eksponensial qidiruv cheklangan ro’yxatlarda ishlaydi , lekin maqsadli qiymat massiv boshiga yaqin joylashgan taqddirdagina ikkilik qidiruvga nisbatan yaxshilanishga aylanadi . 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. Grafiklarga umumlashtirish . Butun sonli ikkilik qidiruv ma’lum turdagi grafiklarda ishlash uchun umumlashtirildi , bunda maqsadli qiymat massiv elementi o’rniga tepada saqlanadi . Ikkilik qidiruv daraxtlar shunday umumlashmalardan biridir - daraxtdagi cho’qqi (tugun ) so’ralganda , algoritm yoki cho’qqining maqsadi ekanligini bilib olamiz . 20 XULOSA. Butun sonli ikkilik qidiruv algoritmi .”Dasturlashning asosiy muommosi – bu murakkablik. Murakkablikni hal qilishning faqatgina bitta yo’li bor: Bo’lib tashla va hukmronlik qil”.Ikkilik qidiruv har bir dasturchi talabaning yoki boshqaning ishini va vaqtini kamaytiradi. Ikkilik dasturda qiyin masalalarni osonlik bilan yechishga imkon beradi. Ikkilik qidirish algoritmi har bir qadamda n ni ikki baravarga kamaytirgani uchun algoritm ishlash tezligi O( logn) hisoblanadi. Solishtirish uchun Facebook misolidagi 1mlrd login ichidan ikkilik qidirish algoritmi 30 ta (!) qadam bilan topishi mumkin. Oddiy qidirishdan tashqari bu algoritmni yana boshqa juda ko’p joyda qo’llash mumkin. ADABIYOTLAR RO’YXATI 1.Misty E Vermaat, Suason L Sebok , Steven M Freund. Discovering Computers (C) 2016 (201edition).Textbook USA , 2016 . 2.Mamarajabov M. , Tursanov S. Kompyuter grafikasi va Web dizayn : Darslik . T.:Cho’lpon, 2013. 3.https://library.ziyonet.uz/uz/book/126181 4.https://library.ziyonet.uz/uz/book/index?Book%5Blevel_id%5D=&Book %5Btype_id%5D=1&Book%5Bcategory_id%5D=53&Book%5Btitle%5D=&Book %5Bdescription%5D=&Book%5Blanguage_id%5D=&yt0=Qidiruv 21

Mavzu:”Butun sonli ikkilik qidiruv algoritmi” MUNDARIJA KIRISH…………………………………………..3 I Bob. Butun sonli ikkilik qidiruvni nazariy asoslari. 1.1.Butun sonli ikkilik qidiruv haqida…………..4 1.2.Algoritm tushunchasi………………………….6 1.3. Muvaffaqiyatli qidiruvlar……………………..7 1.4. Muvaffaqiyatsiz qidiruvlar…………………… 11 II Bob.Butun sonli ikkilik qidiruvni ishlab chiqish..12 2.1. Shovqinli ikkilik qidiruv …………………….12 2.2.Kvant ikkilik qidiruv…………………………..12 2.3. Muqobil protseduraning bajarish……………..15 2.4. Lineer qidiruv………………………………..16 Xulosa…………………………………………..19 ADABIYOTLAR RO’YXATI………………….20

KIRISH Butun sonli ikkilik qidiruv algoritmi . “Dasturlashning eng asosiy muommosi - bu murakkablik . Murakkablik ni hal qilishning faqatgina bitta asosiy yo’li bor : Bo’lib tashla va hukmronlik qil “ -- Bjarni Stroustrup 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 3ta bosqichdan iborat bo’ladi : 1.Bo’lib tashlash bosqichi . Bunda bosh masala huddi shu masalaga o’xshash kichikroq masalalarga bo’lib chiqiladi . 2.Hukmronlik bosqichi . Asos holatimizga mos kelib qolgan qism masalalar huddi u kabi yechiladi . 3.Birlashtirish bosqichi. Bu bosqichda yechiladigan kichik qism masalalar qaytib birlashtirish chiqiladi va bu bosh masala yechimi bo’ladi . I.Bob. Butun sonli ikilik qidiruvni nazariy asoslari . 1.1. Butun sonli ikkilik qidiruv haqida . Algoritm fanida ikkilik qidiruv , shuningdek , yarim intervalli qidiruv ,logarifmik qidiruv yoki ikkilik chop deb nomlanuvchi , tartiblangan massiv ichida maqsadli qiymatning o’rnini topadigan qidiruv algoritmidir. Ikkilik qidiruv maqsadli qiymatni massivning o’rta elementi bilan solishtiradi . Agar ular teng bolmasa , nishon yo’qolmaydigan yarmi yo’q qilinadi. Va qolgan yarmida

qidirish yana davom etadi. Maqsadli qiymat bilan solishtirish uchun o’rta elementi olish va maqsadli qiymat topilguncha buni takrorlash. Agar qidiruv qolgan yarmi bo’sh bo’lishi bilan tugasa , maqsad massivda emas. Ikkilik qidiruv algoritmi. Ikkilik qidiruv algoritmining vizualizatsiyasi. 7 maqsadli qiymatlari Class qidiruv algoritmi Malumotlar tuzilishi massiv Eng yomon ishlash O(log n) Eng yaxshi holat O(1) O’rtacha ishlash O(log n) Eng yomon holatda bo’sh joy Q(1) Ikkilik qidiruv eng yomon holatda logarifmik vaqtda ishlaydi, O(logn) taqqoslashlarni amalga oshiradi, bu yerda n massivdagi elementlari soni. Ikkilik qidiruv kichik massivlardan tashqari chiziqli qidiruvga qaraganda tezroq. Biroq, ikkilik qidiruvni qo’llash uchun massiv avval tartiblangan bo’lishi kerak. Tez qidirish uchun mo’ljallangan maxsus ma’lumotlar tuzilmalari mavjud , masalan , xesh-jadvallar, ularni ikkilik qidiruvdan ko’ra samaraliroq qidirish mumkin. Biroq , ikkilik qidiruv kengroq muommolarni hal qilish uchun ishlatilishi mumkin, masalan, massivda yo’q bo’lsa ham, maqsadga nisbatan massivdagi keyingi eng kichik yoki keyin eng katta elementni topish. Ikkilik qidiruvning ko’plab variantlari mavjud. Xususan , Kasrli kaskad bir nechta massivlarda bir xil qiymat uchun ikkilik qidiruvni tezlashtiradi . Fraksional kaskad hisoblash geometriyasida va boshqa ko’plab sohalarda bir qator qidiruv muommolarini samarali hal qiladi. Eksponensial qidiruv ikkilik qidiruv cheklanmagan ro’yxatlargacha kengaytiradi . Ikkilik qidiruv daraxt va B-daraxt ma’lumotlar tuzilmalari ikkilik qidiruvga asoslangan. 1.2. Algoritm tushunchasi.

Ikkilik qidiruv tartiblangan massivlarda ishlaydi. Ikkilik qidiruvga massivning o’rtasida joylashgan elementlarni bilan solishtirishdan boshlanadi. Agar maqsadli elementga mos kelsa, uning massivdagi o’rni qaytariladi. Agar maqsadli qiymat elementdan kichik bo’lsa, qidiruv massivning pastki yarmida davom etadi. Shunday qilib, algoritm har bir iteratsiyada maqsadli qiymat yotmasligi mumkin bo’lgan yarmini yo’q qiladi. Protecure - jarayon A 0, A 1 ,A 2,: ……………A n-1 qiymatlari yoki yozuvlari bo’lgan n ta elementdan iborat A massivi shunday tartiblanganki, A 0 < A 1 < A 2 <……………..< A n-1 va maqsad qiymat T bo’lsa quyidagi dastur Adagi T indekisini topish uchun ikiklik qidiruvdan foydalaniladi. Function binary_search(A, n, T) is L :=0 R :=n-1 While L<R do, m := floor(L+R)/2 if A(m)< T then L : = m + 1 else if A(m) > T then R : = m - 1 else : return m return unsuccessful Shu bilan bir qatorda , algoritm L+R/2 shiftini olish mumkin.

1.3.Muvaffaqiyatli qidiruvlar . Butun sonli ikkilik qidiruv daraxti ko’rinishda muvaffaqiyatli qidirish ichki yo’l deb ataladigan ildizdan maqsadli tugungacha bo’lgan yo’l bilan ifodalanishi mumkin. Butun sonli ikkilik qidiruv solishtirishlar yordamida qidirish uchun optimal algoritm bo’lganligi sababli, bu muommo n ta tugunli barcha binar daraxtlarning minimal ichki yo’l uzunligi hisoblash uchun qisqartiriladi, bu quyidagilarga teng: I(n) = ∑ k=1 n (log 2 (k)) Masalan, 7 element massivda ildiz bir iteratsiyani talab qiladi, ildiz ostidagi ikkita element ikkita takrorlashni va quyidagi joylashgan to’rtta elementni talab qiladi. Muqobil protsedura Yuqoridagi protsedurada algoritm har bir iteratsiyada o’rta element (m) maqsad (T) ga teng yoki yo’qligini tekshiradi. Ba’zi ilovalar har bir iteratsiya paytida ushbu tekshiruvni o’tkazib yuboradi. Algoritm bu tekshirishni faqat bitta element qolganda (L=R bo’lganda ) amalga oshiradi. Bu tezroq taqqqoslash davriga olib keladi, chunki har biriga bitta taqqoslash o’chiriladi. Hermann Bottenbruch 1962-yilda ushbu tekshiruvni o’tkazib birinchi dasturni nashr etdi. L ni 0 va R n-1 L ga teng emas R 1. m ni (o’rta elementning joylashuvi ) L+R/2 ni o’rnating , kichik butun son L+R/2 dan katta. 2. Agar A m > T, bo’lsa, R ni m-1 ga qo’ying . 3. Aks holda , A m < T; L ni m ga qo’ying. 4. Endi L=R qidiruv amalga oshiriladi. Agar A L = T , bo’lsa L ni qaytaring. Aks holda , qidiruv muvaffaqiyatsiz tugaydi. Shift ceil funksiyasi bo’lsa, ushbu versiyaning psevdokodi: Funksiya binary _search _alternative( A, n, T) L : = 0

Похожие

Haqiqiy ikkilik qidiruv
Qidiruv algoritmlari
INTERPOLATSION QIDIRUV
Dataxtlar, ikki tomonlama daraxtlar, ikkilik daraxtlarning vakilligi, ikkilik daraxtlarning o’tishi
Daraxtlar, ikki tomonlama daraxtlar. Ikkilik daraxtlarning vakili. Ikkilik daraxtlarning o'tishi