AMALIY MASHG’ULOT- 2
Mavzu: Qidiruv algoritmlari: chiziqli va binary qidiruv. Xesh funksiyalar va xesh
algoritmlarini tuzish.
Ishdan maqsad: Ushbu laboratoriya ishining maqsadi
talabalar qanday qidirish
usullari va algoritmlari mavjudligini va ularning samaradorliklarini baholashni
o’rganishlari kerak. Shu asosda qidirish usullarini
qiyosiy tahlil qilishlari, C++
dasturlash tilida qidirish bilan islashni va ularga oid dasturlar tuzishni
o’zlashtirishlari kerak.
Qo’yilgan masala: Talabalar topshiriq variantiga mos
qidirish usuli yordamida
masalani yechish dasturini yaratish ko’nikmasiga ega bo’lishlari kerak.
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.
Endi bundan optimal bo'lgan usul - binar(ikkilik) qidiruvni ko'rib chiqsak. Bu
usulda ham funksiyaga 2
ta parametr, birinchisi massiv o'zi keyin esa biz
qidirayotgan elementni parametr sifatida beriladi. Qidiruv esa quyidagicha:
Dastlab biz massiv boshi va oxirini o'zimiz uchun o'zgaruvchilarda belgilab olamiz,
mening kodimda bu left va right o'zgaruvchilaridir:
left := 0 right := len(a)
so'ngra quyidagi shart bajarilgan holda
left< right
quyidagi ketma-ket operatsiyalarni amalga oshiramiz
1. left va right index lari markazidagi elementni topamiz (left + right) /2
2. topilgan elementimiz biz qidirayotgan elementga teng bo'lsa
unda mid
elementni javob sifatida qaytaramiz
3. 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.
4. 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.
Bu usul binar qidiruvni iterativ usuli deyiladi, shuningdek bu algoritmni rekursiya
usulida ham yozish mumkin, rekursiv usulni erinmasangiz o'zingiz yozib ko'ring.
Bitta urinishda ko'pchilik dasturchilar bu narsani to'g'ri
yoza olishmaydi va bu
normal holat, chunki xato bor joyda o'z ustida ishlash uchun imkoniyat bo'ladi.
Endi bu qidiruv usullarini ayrim jihatlarini keltirib o'tamiz:
5. funksiyaga berilayotgan massiv Binar qidiruv uchun albatta o'sish tartibida
bo'lishi talab qilinadi, chiziqli qidiruv uchun esa berilayotgan massiv qay tartibda
bo'lishini ahamiyati yo'q
6. 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)
