Bizga ushbu massivda biron bir element bor yoki yo'qligini tekshira oladigan dastur tuzish sharti qo'yilgan



Download 17,5 Kb.
Sana12.11.2019
Hajmi17,5 Kb.
#25711
Bog'liq
Bizga ushbu mas-WPS Office

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 - Linear Search deb ataladi, va bu usul kodi quyidagi ko'rinishda:

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 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 leftva right o'zgaruvchilaridur:

left := 0 right := len(a)

so'ngra quyidagi shart bajarilgan holda

left < right

quyidagi ketma-ket operatsiyalarni amalga oshiramiz

left va right index lari markazidagi elementni topamiz (left + right) / 2topilgan elementimiz biz qidirayotgan elementga teng bo'lsa unda mid elementni javob sifatida qaytaramizagar 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.

Shu zaylda qidiruv left < right shart bajarilmagunicha davom etadi, agar bu jarayonda biz qidirgan element topilmasa u xolda -1 javob qaytariladi, quyida dastur kodi keltirilgan:

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 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: 

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'qchiziqli 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)



Bundan tashqari massivda qidirishning boshqa usullari ham mavjud bu haqida bu yerda batafsil bilib olishingiz mumkin.
Download 17,5 Kb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish