Jizzax filiali amaliy matematika fakulteti

Interpolation qidiruv: Ushbu qidiruv algoritmi kerakli qiymatni tekshirish pozitsiyasida ishlaydi. Ushbu algoritm to'g'ri ishlashi uchun ma'lumotlarni yig'ish tartiblangan shaklda va teng taqsimlangan bo'lishi kerak.

QIDIRISH JARAYONI

Chiziqili qidirish algoritmi elementni array boshidan tartib bilan qidiradi. Ikkilik qidirish algoritmida esa bu jarayon array o’rtasidan boshlanib turlicha davom etishi mumkin. Dasturlashda bu jarayon tasodifiy elementga murojaat (random access) deb ataladi. Bu narsa qidirish algoritmi ish bajarayotgan ma’lumot tuzilmasi uchun muhim. Chunki ba’zi tuzilmalarda tasodifiy elementga birdan murojaat qilishning iloji yo’q. Masalan, stack, queue, linked list shu kabilardir.

SOLISHTIRISH

Elementni qidirishda solishtirish jarayoni ham ikki xil bo’ladi. Chiziqli qidirish algoritmi faqat tenglikka asoslanadi. Ikkilik qidirish esa tenglik, katta yoki kichiklikka qarab, o’z ishini davom ettiradi.

VAQT BO’YICHA MURAKKABLIK

Ikkita bir xil vazifani bajaruvchi algoritmlarni solishtirayotgan paytda ularning ishlash tezligini solishtirib ko’rmasdan iloj yo’q.
Chiziqli qidirish ishlash tezligi:
Eng yaxshi holatda: O(1)
O’rtacha holatda: n(n+1)/2n = O(n)
Eng yomon holatda: O(n)
Ikkilik qidirish ishlash tezligi:
Eng yaxshi holatda: O(1)
O’rtacha holatda: logn(logn+1)/2logn = O(logn)
Eng yomon holatda: O(logn)
Element tasodifiy tartibda massivda va biz elementni topishimiz kerak deb faraz qilaylik. Keyin maqsadli elementni qidirishning yagona yo'li birinchi pozitsiyadan boshlash va uni maqsad bilan solishtirishdir. Agar element bir xil bo'lsa, biz joriy elementning o'rnini qaytaramiz. Aks holda, biz keyingi pozitsiyaga o'tamiz. Agar biz massivning oxirgi pozitsiyasiga etib kelsak va hali ham maqsadni topa olmasak, biz -1 ni qaytaramiz.
Bu chiziqli qidiruv yoki ketma-ket qidiruv deb ataladi. A-X dan berilgan tartiblangan roʻyxatdagi “J” elementini topish uchun chiziqli qidiruv




A
-X dan berilgan tartiblangan roʻyxatdagi “J” elementini topish uchun ikkilik


Ma'lum bo'lgan narsani topish noma'lum narsani qidirayotgan 'tadqiqot' deb ataganimizdan farqli o'laroq 'qidiruv' deb ataladi. Nomidan ko'rinib turibdiki, AI qidirish algoritmlarining vazifasi ham qidirishdir. Muammoni hal qilish-bu qidiruvning to'g'ridan-to'g'ri qo'llanilishi. AI qidirish algoritmlari yordamida real muammolar uchun samarali va samarali echimlarni shakllantirish mumkin.
Algoritmlarga chuqur kirib borishdan oldin, avvalo, muammoning mohiyatini va ba'zi bir terminologiyani tushunishimiz kerak. Odatda, muammo davlatlar, harakatlar/operatsiyalar, maqsadlar, yo'l sifatida 04 ta asosiy komponentdan iborat. Sodda qilib aytganda, muammoni hal qilish harakatlar yoki operatsiyalar orqali bir qator holatlarni yo'l/yo'llar bo'ylab maqsadga aylantirishni o'z ichiga olgan jarayon sifatida aniqlanishi mumkin.
Davlat-makon muayyan muammoni hal qilish bo'yicha harakatlar bilan birga barcha mumkin bo'lgan holatlardan iborat. Davlat makonining grafik tasvirida (masalan, daraxtlar) holatlar tugunlar bilan, harakatlar esa yoylar bilan ifodalanadi. Har qanday holat maydonida boshlang'ich tugun "boshlanish" va yakuniy tugun "maqsad" yoki bir nechta "maqsad"holatlari mavjud. Dastlabki boshlang'ich tugundan yakuniy maqsadli tugungacha bo'lgan yo'l ma'lum bir muammoni "hal qilish" deb nomlanadi.


Binary qidiruvda joylashishni aniqlash
Ikkilik qidiruvda, agar kerakli ma'lumotlar topilmasa, qolgan ro'yxat ikki qismga bo'linadi, pastki va yuqori. Qidiruv ularning har birida olib boriladi.





Ma'lumotlar tartiblangan bo'lsa ham, ikkilik qidiruv istalgan ma'lumotlarning o'rnini tekshirish uchun foyda keltirmaydi.