Chiziqli va binar qidiruv
Salom! Ushbu maqolada men massivda biron bir elementni qidirish algoritmlari bilan qisqacha tanishtirishga harakat qilaman.
Aytaylik bizga massiv berilgan:
a := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Bizga ushbu massivda biron bir element bor yoki yo'qligini tekshira oladigan dastur tuzish sharti qo'yilgan.
Ushbu masalani yechishda eng birinchi xayolga keladigan usul - bu massivni ketma-ket har bir elementini solishtirib chiqish va bu usul:
Chiziqli qidiruv -
func linearSearch(a []int, condidate int) int { for i := 0; i < len(a); i++ { if a[i] == condidate { return i } } return -1 }
Ko'rib turganingizdek, funksiyamiz 2
Endi bundan optimal bo'lgan usul - binar(ikkilik) qidiruvni ko'rib chiqsak.
Bu usulda ham funksiyaga 2
Dastlab biz massiv boshi va oxirini o'zimiz uchun o'zgaruvchilarda belgilab olamiz, mening kodimda bu
left := 0 right := len(a)
so'ngra quyidagi shart bajarilgan holda
left < right
quyidagi ketma-ket operatsiyalarni amalga oshiramiz
left varight 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 bizleft =mid deb belgilaymiz va shundaa [mid :right ] bo'lagida qidiruv davom etadi. - agar
a [mid ] elementimiz biz qidirayotgan elementdan katta bo'lsa demakright =mid deb belgilaymiz shunda qidiruva [left :mid ] bo'lagida qidiruv davom etadi.
Shu zaylda qidiruv
func binarySearch(a []int, condidate int) int { left := 0 right := len(a) for left < right { mid := (left + right) / 2 if a[mid] == condidate { return mid } if a[mid] < condidate { left = mid } else { right = mid } } return -1 }
Bu usul binar qidiruvni
Endi bu
qidiruv usullarini ayrim jihatlarini keltirib o'tamiz:
- 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
- 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 bilanO (n ) va binar qidiruvniki ko'pi bilanO (log n )
Bundan tashqari massivda qidirishning boshqa usullari ham mavjud bu haqida bu yerda batafsil bilib olishingiz mumkin.
Xato kamchiliklar bo'lsa izohda qoldiring!
Vaqt ajratganingiz uchun katta rahmat!
Birinchi bo‘ling!