Mavzu: Ma’lumotlar turlari va algoritmlari, ma’lumotlarni qidirish usullari, algoritmlar va ularning samaradorligi

Kompyuter va kompleks tizimlarida ma’lumotlarni qayta ishlashda qidiruv asosiy va keng foydalanadigan amallardan biri hisoblanadi.

QIDIRUV bu ma’lumotlarning orasidan ma’lum bir belgilarga mos ma’lumotlarni topish yoki yo’qligini aniqlash jarayonidir.

Qidiruvning maqsadi - quyidagi jarayonlarning birini bajarilishidan iborat:

• topilgan yozuvni oʼqish;
• qidirilayotgan yozuv topilmasa, uni jadvalga qoʼshish;
• topilgan yozuvni oʼchirish.

Qidiruv tushunchasi va uning vazifasi

Qidiruvni amalga oshirayotganda 3ta xususiyat (atribut) ajratish mumkin:

1) Ma’lumotlar majmuasi - bu fayl yoki jadval ko’rinishidagi berilgan ma’lumotlar jamlanmasi (to’plami).

2) Kalit - ixtiyoriy maʼlumot (yoki tuzilma elementi) boshqa maʼlumotdan biror bir farqlash belgisi.

3) Qidiruv mezoni – bu qidirilayotgan kalit belgisi ma’lumotlar yozuvlarida moslik sharti. (teng, yaqin, o’xshash va b.)

Kalit ikki hil boʼlishi mumkin:

* Birlamchi (takrorlanmaydi, noyob);

* Ikkilamchi (takrorlanadi).

Kalitlar saqlanishiga nisbattan ichki va tashqi deyiladi. Agar kalitlar maʼlumotlar jadvalidan ajratib olinib alohida fayl sifatida saqlansa, u holda bunday kalitlar tashqi kalitlar deyiladi. Аks holda, yaʼni yozuvning bir maydoni sifatida jadvalda saqlansa ichki kalit deyiladi.

Qidiruv usullari va algoritmlari

Jadvaldagi maʼlumotlarning tuzilmasiga qarab qidiruvni bir necha turlari mavjud:

• Chiziqli yoki ketma-ket qidiruv (Linear search)
• Binar yoki oraliqni teng ikkiga bo’lish orqali qidiruv (Binary search)
• O’tish yoki o’tqazishlar orqali qidiruv (Jump search)
• Xeshlash yoki kalitlarni akslantirish orqali qidiruv (Hash-based Search)

Chiziqli yoki ketma-ket qidiruv (Linear search)

Izoh: algoritmdan ixtiyoriy tartibda joylashgan maʼlumotlar jadvalida foydalanish mumkin.