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

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.