Axborot qidirish – bu kognitiv psixologiya, informatika, axborot dizayni, lingvistika (tilshunoslik), semiotika va kutubxonashunoslik kabi fanlar kesishmasida turuvchi ilmiy soha hisoblanadi.
Axborotni qidirish masalalari
AQ ning asosiy masalasi – foyalanuvchiga uning axborotga bo’lgan ehtiyojlarini qondirishga yordam berishdan iborat. Asosiy masalalar:
-Axborotlarni ajratib olish, xususiy holda hujjat annotatsiyasi va referatini tayyorlash;
- So’rov tillari va boshq.
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.
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.
Binar qidiruv
Qiyinlik darajasi: 5/10.
Eng zo'r ko'rsatkichi(vaqt): O(1)
Eng yomon ko'rsatkichi(vaqt): O(log n)
O'rtacha ko'rsatkichi(vaqt): O( log n)
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.
Masalan:
Biz bitta taqqoslashdan so'ng massivning yarim elementlarini hisobga olmasak ham bo'ladi.
1. x ni o'rtadagi element bilan solishtiramiz.
2. Agar rost bo'lsa, o'rtadagi elementni qaytaramiz.
3. Agar x katta bo'lsa, x ni massivni o'ng yarmini ichidan qidiramiz, yuqoridagi ketma-ketlikni bajargan holda.
4. Aks holda chap yarmi bilan binar qidiruvni amalga oshiramiz.
Quyida Binar qidiruvning rekursiya orqali amalga oshiramiz.
// C++ tilida rekursiyali Binar Qidiruv
#include // Rekursiyali qidiruv funksiyasi. U massivdan
// x qaysi o'rinda turganini qaytaradi,
// yoki -1
