Toshkent 2020 Variant №: 15

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

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.
   

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