4-mavzu: Ma’lumotlarni qidirish usullari, algoritmlari va ularning samaradorligi

Chiziqli yoki ketma-ket qidiruv (Linear search)

• Izoh: algoritmdan ixtiyoriy tartibda joylashgan maʼlumotlar jadvalida foydalanish mumkin.
• ALGORITM G’OYASI:
• Ma’lumotlarning birinchi elementidan oxirgi ementiga qadar ketma-ket qarab chiqiladi va har qadamda element qidirilayotgan kalit bilan taqqoslanadi. Agar element kalitga mos bo’lsa jarayon to’xtatiladi. Agar oxirgi element ko’rib chiqilganda jarayon to’xtatilmagan bo’lsa u xolatda ma’lumot topilmaganligini anglatadi.

Chiziqli yoki ketma-ket qidiruv

• Bu yerda:
• arr[] – ma’lumotlar to’plami
• key – qidirilayotgan ma’lumot

Binar yoki oraliqni teng ikkiga bo’lish orqali qidiruv (Binary search)

• Izoh: algoritmdan faqatgina maʼlumotlar jadvali tartiblangan boʼlsagina foydalanish mumkin.
• ALGORITM G’OYASI:
• Berilgan massiv oʼrta elementi tanlanadi, va qidirilayotgan kalit bilan taqqoslanadi. Аgar tanlangan element qiymati qidirilayotgan kalit qiymatiga teng boʼlsa, u holda qidiruv yakunlanadi; agar tanlangan elementi qiymati qidirilayotgan kalit qiymatidan kichik boʼlsa, u holda chap tomonda elementlar kelgusi qidiruvdan chiqarib yuboriladi va algoritm qayta ishga tushadi. Xuddi shuningdek, agar tanlangan elementi qiymati qidirilayotgan kalit qiymatidan katta boʼlsa u holda o’ng tomonda elementlar kelgusi qidiruvdan chiqarib yuboriladi va algoritm qayta ishga tushadi. Agar ikkita chegara orasida elementlar qolmasa u xolatda ma’lumot topilmaganligini anglatadi va jarayon to’xtatiladi.

Binar yoki oraliqni teng ikkiga bo’lish orqali qidiruv (Binary search)

Binar yoki oraliqni teng ikkiga bo’lish orqali qidiruv (Binary search)

O’tish yoki o’tqazishlar orqali qidiruv (Jump search)

• Izoh: algoritmdan faqatgina maʼlumotlar jadvali tartiblangan boʼlsagina foydalanish mumkin.
• ALGORITM G’OYASI:
• Belgilangan bosqichlarda sakrash, ya'ni elementlarning ba'zi bloklarini o'tkazib yuborish orqali (chiziqli qidiruvdan ko'ra) kamroq elementlarni tekshirishdir. Bloklarni o’tqazish uchun qadami ildiz osti N-ga teng. N – ma’lumotlarning umumiy soni.

• Key = 78