|
Oqituvchi: Akbarova Marg’uba
|
| bet | 4/5 | | Sana | 13.12.2023 | | Hajmi | 1,25 Mb. | | #117905 |
Bog'liq malumotlar tuzilmasiint n = sizeof(arr)/ sizeof(arr[0]);
int x = 10;
int natija = binarqidiruv(arr, 0, n-1, x);
(natija == -1)? printf("X soni massiv ichida topilmadi.")
: printf("X soni massivning %d o'rnida.", natija);
return 0;
}
Chiziqli va binar qidiruv
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 - 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 left va 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) / 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.
|
| |
