2-ma’ruza. Qidiruv va xeshlash algoritmlar. Qidiruv algoritmlar: chiziqli algoritm, tartiblangan navbatlar, binary qidiruv

2-ma’ruza. Qidiruv va xeshlash algoritmlar. Qidiruv algoritmlar:chiziqli algoritm, binary qidiruv algoritmi.

• Reja:
• Qidiruv masalalari. Qidiruv Abstraksiyasi;
• Ketma-ket qidiruv algoritmlari;
• Oraliqni (hududni) qisqartirish usulida izlash algoritmi;
• Taqsimlangan qidirish algoritmlari;
• Xesh jadval tushunchasi;
• Xeshlash usuli qo’llaniladigan sohalar;

Qidiruv masalalari

• Qidiruv masalasini shakllantirish quyidagicha bosqichda amalga oshiriladi:
• 1-bosqichda. Ma’lumotlarni yig’ish, to’ldirish.
• 2-bosqichda. Ma’lumotlarni tashkil etish (tartiblash va saralash);
• 3-bosqichda. Ma’lumotlarni olish (hususiy qidiruv);

Talablari:

• Katta hajmli axborotlarni qo’llab quvvatlashi;
• Ma’lumotlarni tezkor topish imkoniyati;
• Tezkor modifikatsiyalash shuningdek ochirish imkoniyati;

Abstraksiyalash uslublari (metodlari)

• – Create xotiraga yangi yozuv qo’yish;
• – Read kalit bo’yicha ma’lumotlarni qidirish.
• – Update kalit bo’yicha ma’lumotlarni yangilash.
• – Delete ma’lumotlarni o’chirish.

Umumiy holda qidiruv masalasini quyidagicha talqin etiladi:

• a1, a2, a3,…,an kalitlar to’plami berilgan bo’lsin. key qiymatiga mos bo’lgan kalit indeksini aniqlash.
• To’plam a;
• index = a.find(key);

Mavjud qidiruv algoritmlari

Bizga massiv berilgan bo’sin:

• a := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
• Ushbu masalani yechishda eng birinchi xayolga keladigan usul - bu massivni ketma-ket har bir elementini solishtirib chiqish va bu usul:
• Chiziqli qidiruv - Linear Search deb ataladi, va bu usul kodi quyidagi ko'rinishda:

Ko'rib turganingizdek, funksiyamiz 2 ta parametr qabul qiladi, birinchisi massivni o'zi, ikkinchisi esa biz qidirayotgan element. Agar uni topa olmasak, "-1" qiymatni qaytaramiz.

Masalan: chiziqli qidiruvga oid misol

2-misol: chiziqli qidiruv

Ikkilik qidiruv

• left va right index lari markazidagi elementni topamiz (left + right) / 2
• topilgan elementimiz biz qidirayotgan elementga teng bo'lsa unda mid elementni javob sifatida qaytaramiz
• agar a[mid] elementimiz biz qidirayotgan elementdan kichkina bo'lsa biz left = mid deb belgilaymiz va shunda a[mid:right] bo'lagida qidiruv davom etadi.
• agar a[mid] elementimiz biz qidirayotgan elementdan katta bo'lsa demak right = mid deb belgilaymiz shunda qidiruv a[left:mid] bo'lagida qidiruv davom etadi.

chiziqli qidiruvda elementlarni bittalab har birini tekshiriladi, binarda esa algoritmidan kelib chiqib chiziqliga nisbatan ancha kam solishtirish amali bajariladi, chiziqli qidiruvning ishlash vaqti ko'pi bilan O(n) va binar qidiruvniki ko'pi bilan O(log n)

Ikkilik (Binar) qidiruv

Jump (sakrab) qidirish algoritmi

• Ikkilik qidiruv singari, Jump Search ham saralangan massivlarni qidirish algoritmidir.
• Asosiy g'oya shundan iboratki, kamroq elementlarni tekshirish (chiziqli qidiruvdan ko'ra) sakrash qadamlar bilan tekshirish yoki barcha elementlarni qidirish o'rniga ba'zi elementlarni o'tkazib yuborish. Faqat tartiblangan massivlarda ishlaydi. Sakrab o'tiladigan blokning optimal hajmi (√ n).
• Algorimning samaradorligi O (√ n)
• Jump Search samaradorligi Liner Search

((O (n)) va Binary Search (O (Log n)) o'rtasida. https://www.geeksforgeeks.org/jump-search/

lys[0], lys[0+jump], lys[0+2jump], lys[0+3jump] va x.