Chiziqli qidirish usulini tadqiq qilish

MUHAMMAD AL-XORAZMIY NOMIDAGI TOSHKENT AXBOROT TEXNOLOGIYALARI UNIVERSITETI Malumotlar tuzilmasi va algoritmlar fanidan 240-21-guruh talabasi Ergashev Jaxongirning “Binar qidirish usulini tadqiq qilish”mavzusi bo`yicha tayyorlagan taqdimoti

Chiziqli qidirish usulini tadqiq qilish

Reja: 1. Ma'lumotlarni qidirish. 2.Chiziqli qidiruv. 3.Binar qidiruv. 4.Chiziqli va binar qidiruv usullarining farqlari va afzalliklari. 5.Xulosa. 6.Foydalanilgan adabiyotlar.

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 malumotlar 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 qidirshga aytiladi. Hozirgi davrda qidiruv algoritmlarisiz ishaydigan IT tizimlar deyarli mavjud emas.

Ma’lumotlarni qidirish algoritimlari 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 qayta-qayta qidiruv tuzilmasi markaziga yo’naladi va qidiruv maydonini ikkiga bo’ladi. Masalan, Binar qidiruv.

CHIZIQLI QIDIRUV

Chiziqli qidiruv tarkibiy qidiruvga misol bo'ladi. Aytaylik bizga massiv berilgan: A={1,2,3,4,5,6,7,8,9,10} Bizga ushbu massivda biron bir element bor yoki yo'qligini tekshira oladigan algoritm tuzish sharti qo'yilgan.Ushbu masalani yechishda eng birinchi hayolga keladigan usul - bu massivni ketma-ket har bir elementini solishtirib chiqish va bu usul: Chiziqli qidiruv - Linear Search deb ataladi. Algoritm g'oyasi: Ma'lumotlar butun jadval bo'yicha operativ xotirada kichik adresdan boshlab, to katta adressgacha ketma-ket qarab chiqiladi.

Chiziqli qidiruv – ixtiyoriy funksiyaning qandaydir kesmadagi berilgan qiymatini qidirishga aytiladi. Bu algoritm oddiy algoritm hisoblanib, boshqa algoritmlardan, masalan binar qidiruvdan farqli tamoni funksiyaga hecha qanday cheklanish qo’yilmaydi va amalga oshirish oddiy hisoblanadi.
Chiziqli qidiruv algoritmi
Funksiya qiymatini izlash navbatdagi qiymatni (odatda chapdan o’nga argument oshishi tartibida amalga oshiriladi)oddiy taqqoslash orqali tekshiriladi. Masala ikki xil qo’yilishi mumkin: 1) Birinchi topilgan argumentni topish 2) Barcha argumentlarni topish.
Agar funkisya sifatida massiv argument sifatida massiv indeksi qo’llanilsa u holda chiziqli qidiruv natijasida berilgan massivdan bo’lgan shunday i indekslarni topish lozim.
Massiv: 45, 12 , 89, 12, -78, 12;
12 sonining pozitsiyalari 2, 4, 6
Bugun sizlar bilan qidirish algoritmlarining eng soddasi bo’lgan chiziqli qidirish algoritmi haqida gaplashamiz. Bu algoritm chiziqli ma’lumotlar tuzilmalaridan (masalan, array) biror bir shart yoki qiymat bo’yicha element qidirishga mo’ljallangan.
Chiziqli qidirish algoritmi qanday ishlaydi?
Aytib o’tganimizdek, bu algoritm juda ham sodda ishlaydi va tasavvur qilishga ham oson. Arrayning birinchi elementidan tekshirish boshlanadi.Element olinadi va u berilgan shartga tekshirib ko’riladi.Agar shartni qanoatlantirsa, uning qiymati yoki joylashgan o’rni (qiymati yoki shunchaki true) qaytariladi va algoritm tugaydi.
Shart qanoatlantirilmasa, keyingi elementga o’tiladi va 2-qadamga qaytiladi
Array tugab, element topilmasa, buni anglatuvchi qandaydir qiymat qaytariladi (-1 yoki false…)
Ko’rinishidan ko’pdek tuyulsa ham, aslida bu algoritm hayotdagi odatiy qidirish bilan bir xil ishlaydi. Keling uni visual holda tasavvur qilamiz.