Mundarija Kirish. Qidiruv algoritmlari ............................................................................................. 2 I bob. Chiziqli qidiruv ..................................................................................................... 5 1.1.Chiziqli qidiruv algoritmi ishlashi ............................................................................. 5 1.2.Chiziqli qidiruv algoritmining c++ tilida dasturi ....................................................... 6 1.3.Chiziqli qidiruv algoritmining murakkabliklari ......................................................... 7 II bob. Ikkilik qidiruv algoritmi ....................................................................................... 7 2.1.Ikkilik qidiruv algoritmi ishlashi ............................................................................... 7 2.2.Ikkilik qidiruv algoritmining c++ tilida dasturi ....................................................... 10 2.3.Ikkilik qidiruv algoritmining murakkabligi ............................................................. 11 III BOB.Satrlarda qismiy satrlarni qidirish algortmlari. ................................................ 11 3.1 Qismiy satrlarni qidirish algoritmlarining turlari ................................................... 13 3.2.Kenglik bo’yicha izlash algoritmi(bfs). ................................................................... 19 3.3.QISMIY SATRLARNI QIDIRISH ALGORITMI ............................................................. 20 XULOSA ........................................................................................................................ 22 Manbalar ..................................................................................................................... 23 1

Kirish. Qidiruv algoritmlari Ro‘yxatdan zarur axborotni qidirish - nazariy dasturlashning fundamental masalalaridan biri hisoblanadi. Qidiruv algoritmini tahlil qilishda, qidirilayotgan axborot kompyuterda ma‘lumotlar massivi ko‘rinishida joylashgan deb faraz qilamiz. Yozuvlar yoki ro‘yxat elementlari massivda ketma-ket joylashadi va ular o‘rtasida bo‘shliq yo‘q. Ro‘yxatdagi yozuvlar 1 dan N gacha tartiblangan bo‘ladi. Aslida yozuvlar maydonlardan tashkil topgan bo‘ladi, bizni kalit deb ataluvchi maydonlardan bittasining qiymati qiziqtiradi. Ro‘yxatlar kalit maydonlari qiymati bo‘yicha tartiblangan yoki tartiblanmagan bo‘lishi mumkin. Aniq qiymatni qidirish masalasi biror elementni tanlash masalasi bilan bog‘liq. Aytaylik, bizga kattaligi bo‘yicha beshinchi element, oxiridan yettinchi yoki o‘rta qiymatli element kerak. Qidiruv - bu kompyuter xotirasida ma‘lumotlarni qayta ishlash jarayonida qo‘llaniladigan asosiy amallardan biri hisoblanadi. Bu amalning mazmuni shundan iboratki, berilgan argument bo‘yicha massiv elementlari orasidan shu argumentga mos ma‘lumotni (elementni) aniqlashdan iborat. Ixtiyoriy ma‘lumot (yoki tuzilma) elementi qandaydir belgisi bilan boshqasidan farq qiladi. Ushbu belgi kalit deyiladi. Kalit takrorlanmas bo‘lishi mumkin, ya‘ni tuzimadagi mavjud bitta element uchun aynan shu kalit qo‘llaniladi. Bunday kalit birlamchi deb ataladi. Elementlarning ma‘lum guruhi uchun takrorlanishi mumkin bo‘lgan kalit ikkilamchi kalit deyiladi, ushbu kalit bo‘yicha ham qidiruv tashkil qilish mumkin. Ma‘lumot elementlarining kalitlari alohida joyda to‘plangan (boshqa jadvalda) bo‘lishi yoki o‘zi alohida yozuvdagi biror bir maydonda saqlanishi mumkin. Bunday ajratib olingan yoki alohida faylda saqlanadigan tashqi kalit deyiladi. Agar kalit yozuvda joylashgan bo‘lsa, u holda ichki kalit deyiladi. Berilgan argument bo‘yicha qidiruv berilgan argument kaliti bilan aniqlangan algoritm deyiladi. Qidiruv algoritmi ishlashi natijasi ushbu ma‘lumotda joylashishi mumkin yoki u jadvalda mavjud bo‘lmasligi mumkin. Ma‘lumotning mavjud bo‘lmaslik holati ikkita amalda yuz berishi mumkin: berilgan qiymatning yo‘qligini aniqlashda; berilgan qiymatni jadvalga qo‘yishda. Masalan, bizga ro‘yxat elementi kaliti sifatida k berilgan bo‘lsin. Har bir k(i) kalitda r(i)- ma‘lumot mavjud. Qidiruv argumenti - Key . Unga yozuv ma‘lumoti rec mos keladi. Jadvalda ma‘lumotlar tuzilmasiga bog‘liq holda qidiruvning bir nechta shakllari farqlanadi. Bu masalani yechish uchun ikki xil yondoshuv mavjud: ketma-ket qidiruv va indeksli ketma-ket qidiruv. Ushbu qidiruv algoritmlarini o‘rganib chiqamiz. 2

Qidiruv algoritmlarida biror aniq elementni mavjud ro‘yxat elementlarini birma-bir qarab chiqish orqali qidirib topish masalasi hal qilinadi. Ketma-ket qidiruv algoritmida ro‘yxatning saralanganligi ahamiyatga ega bo‘lmasa-da, lekin saralangan ro‘yxatda eng yaxshi natijaga erishiladi. Odatda qidiruv kerakli elementning ro‘yxatda bor yoki yo‘qligini shunchaki tekshirish uchun emas, balki shu kalit- qiymatga ega bo‘lgan ma‘lumotni ajratib olish uchun ham qo‘llaniladi. Masalan, kalit-qiymat qidirilayotgan elementning tartib raqami yoki boshqa unikal (yagona) identifikator bo‘lishi mumkin. Kerakli kalit topilgandan so‘ng dastur shu kalitga mos ma‘lumotlarni o‘zgartirishi yoki shunchaki barcha yozuvlarni ajratib chiqarishi mumkin. Har qanday holatda ham qidiruv algoritmi kalitning joylashgan o‘rnini aniqlash masalasini yechish uchun qo‘llaniladi. SHuning uchun ham qidiruv algoritmlari kerakli kalitdan tarkib topgan yozuv indeksini natija sifatida ajratib beradi. Agar kalit-qiymat topilmasa, u holda qidiruv algoritmi massivning yuqori chegarasidan katta bo‘lgan indeks qiymatini qaytaradi. Maqsadga erishish uchun ro‘yxat elementlari 1 dan N gacha bo‘lgan sonlar yordamida raqamlangan bo‘lsin deb faraz qilamiz. Bu holatda qidirilayotgan kalit ro‘yxatda mavjud bo‘lmasa, algoritm 0 qiymatni beradi (1-rasm). Soddalik uchun ajratib olinadigan kalit-qiymatlar ro‘yxatda takrorlanmaydi deb qabul qilinadi. Ketma-ket qidiruv algoritmi ro‘yxatning birinchi elementidan boshlab oxirgi elementgacha qidirilayotgan elementni topilmaguncha qarab chiqiladi. Bundan kelib chiqadiki, kalit qiymati ro‘yxatda qancha uzoqda turgan bo‘lsa, qidiruv shuncha uzoq davom etadi (vaqtga nisbatan). Bu holatni ketma-ket qidiruv algoritmi tahlilida e‘tiborga olish zarur bo‘ladi. Algoritmning tahlili. Ketma-ket qidiruv algoritmida ikki eng yomon holat mavjud. Birinchi holatda qidiruvdagi element ro‘yxat oxirida joylashgan bo‘ladi. Ikkinchi holatda esa, qidiruvdagi element ro‘yxatda mavjud bo‘lmaydi. Har ikki holatda ham necha marta taqqoslash amali bajarilishini qarab chiqamiz. Ro‘yxat elementlarining kalit qiymati unikal (takrorlanmas) deb qaraydigan bo‘lsak, qidiruvdagi elementga moslik oxirgi yozuvda uchrasa, u holda oxirgi taqqoslash keraksiz bo‘lishi mumkin. 31-rasm

Lekin algoritm oxirgi elementga qadar taqqoslash amalini bajaradi. Natijada N ta taqqoslash amalga oshiriladi (bu yerda N - ro‘yxatdagi elementlar soni). Qidirilayotgan qiymatning ro‘yxatda yo‘qligini tekshirish uchun uni ro‘yxatning barcha elementlari bilan taqqoslab chiqishga to‘g‘ri keladi. Agar biror element bilan taqqoslash qoldirilsa, u holda qidirilayotgan element rostdan ham ro‘yxatda yo‘qligini aniqlab bo‘lmaydi. Bu esa ro‘yxatning barcha elementlarini qarab chiqishni talab etadi va bu holatda ham N marta taqqoslash amalga oshiriladi. Umuman olganda, qidirilayotgan element ro‘yxatning oxirgi elementi yoki unda mavjud emasligini aniqlash uchun N marta taqqoslash amali bajariladi. N har qanday qidiruv algoritmining eng yuqori chegarasi hisoblanadi, agar taqqoslashlar N dan ko‘p bajarilsa, hech bo‘lmaganda ro‘yxatning bitta elementi bilan ikki marta taqqoslash bajarilganligini bildiradi. Bundan kelib chiqadiki, ortiqcha ish bajarilgan va algoritmni yaxshilash talab etiladi. O’rtacha holat tahlili. Qidiruv algoritmi uchun ikkita o‘rtacha holat mavjud. Birinchi holatda qiqdiruv muvaffaqiyatli, ikkinchi holatda qidiruv samarasiz, ya‘ni qidirilayotgan element ro‘yxatda mavjud bo‘lmasligi mumkin. Agar qidirilayotgan element ro‘yxatda bo‘lsa, u holda N marta mumkin bo‘lgan holatlardan biriga teng bo‘ladi: birinchi, ikkinchi, uchinchi va h.k. Bu holatlarning barchasini teng ehtimolli deb faraz qilamiz, ya‘ni qidirilayotgan element mavjud holatlarning birida uchrashi ehtimoli 1/N ga teng bo‘ladi. Ushbu xulosalardan kelib chiqqan holda quyidagi savollar tug‘iladi: Agar qidirilayotgan element ro‘yxatda birinchi turgan bo‘lsa, necha marta taqqoslash bajariladi? Ikkinchi bo‘lsa-chi? Uchinchisi bo‘lsa-chi? N -element bo‘lsa-chi? Agar yuqorida aytilgan fikrlardan kelib chiqadigan bo‘lsak, ushbu savollarga javob tayyor, chunki har bir holat uchun mos ravishda 1, 2, 3 va N marta taqqoslash bajariladi. Bu esa N ta holatdan har biri qidirilayotgan elementning ro‘yxatda joylashish tartibiga mos kelishini bildiradi. Natijada, o‘rtacha holatlar uchun quyidagi tenglikga erishamiz: A(N) = 1 f , = 1. N(N + 1) = N +1 , (i) N : N 2 2 ' ’ Agar qidirilayotgan element ro‘yxatda mavjud bo‘lmasa taqqoslashlar soni N+ 1 gacha oshib ketadi. Element ro‘yxatda mavjud bo‘lmasa, u holda qidiruv uchun N ta taqqoslash zarurligini yuqorida ko‘rib chiqdik. Agarda ro‘yhat elementlari soni N juda katta son bo‘lsa u holda 1/( N +1) ning qiymati 0 ga yaqin son bo‘ladi. 4

Bu qidirish usulida ikkita jadval tashkil etiladi: o‘z kalitlariga ega bo‘lgan ma‘lumotlar jadvali (o‘sish tartibida joylashtirilgan) va ma‘lumotlar kalitlaridan tashkil topgan indekslar jadvali. Bu kalitlar asosiy jadvaldan oldindan aniqlangan intervalda olinadi (2-rasm) Bu yerda birinchi berilgan argument bo‘yicha indekslar jadvalidan ketma- ketlikda qidirish amalga oshiriladi. Kalitlarni ko‘rib chiqishda berilgan kalitdan kichigi topilsa, u holda ushbu kichik kalitni asosiy jadvaldagi qidirishning eng quyi chegarasi - low ga joylashtiramiz, xuddi shunday berilgan kalitdan katta deb topilgan kalitni ( kind > key ) yuqori hi ga joylashtiramiz. Misol uchun, key = 101. Algoritmning tahlili . Agar barcha holatlar uchun teng ehtimollik deb hisoblansa, u holda qidirish samaradorligini quyidagicha aniqlash mumkin. I bob. Chiziqli qidiruv Chiziqli qidiruv - ketma-ket qidiruv algoritmi bo'lib, biz bir uchidan boshlaymiz va kerakli element topilgunga qadar ro'yxatning har bir elementini tekshiramiz. Bu eng oddiy qidiruv algoritmidir. 1.1.Chiziqli qidiruv algoritmi ishlashi Quyidagi ro'yxatdagi elementni qidirish uchun quyidagi bosqichlar bajariladi k = 1 . 52-rasm. Indeksli ketma-ket qidirish usuliga misol .