B erdaq nomidagi qoraqalpoq davlat universiteti

Mavzu:Chiziqli va Binar izlash

Ishning maqsadi:Chiziqli va Binar algoritmlar bilan tanishish va ularni e`lon qilish

Nazariy qism:1|2|3|4|5|6|7|8|9|10

Bizga massiv berilgan:

a:=[]int{1,2,3,4,5,6,7,8,9,10}

Bizga ushbu massivda qaysidir element bor yoki yo`qligini tekshiruvchi dastur tuzish qo`yilgan bo`lsin.Bu masalani yechishda birinchi o`ylaydigan usulimiz bu massivning har bir elementini solishtirib chiqish.

Chiziqli izlash – Linear Search deb ataladi va bu usul kodi quyidagicha

Func linearSearch(a []int,condidate int)

int { for i=0;i

{if a[i]==condidate {return i}

}

return -1

}

Ko`rib turganimizdek funksiyamiz 2 parametr qabuk qiladi. Birinchisi massivning o`zi, ikkinchisi biz izlayotgan element. Agarda u topilmasa -1 qiymatni qaytaramiz.Endi bu usuldan optimal bo`lgan binar ya`ni ikkilik usulni ko`ramiz. Bu usulda ham funksiyaga 2 parametr, birinchisi massivning o`zi keyingisi esa biz izlayotgan element. Izlash quyidagicha amalga oshiriladi:

Oldin biz massivning birinchi va oxirgi elementlarini o`zimiz uchun o`zgaruvchilarni belgilab olamiz.Ushbu kodda bu o`zgaruvchilar

left:=0 right:=len(a)

Quyidagi shart bajarilgan holda

left

Quyidagi ketma-ketliklarni amalga oshiramiz:

Left va right indekslari markazidagi elementni topamiz (left+right)/2

Topilgan element biz izlayotgan elementga teng bo`lsa, unda mid elementni javob sifatida joylashtiramiz. Agar a[mid] elementimiz biz izlzyotgan elementdan kichik bo`lsa biz left=mid deb belgilaymiz, keyin a[mid:right] qismida izlash davom etadi. Agar a[mid] elementimiz biz izlayotgan elementdan katta bo`lsa demak right=mid deb belgilaymiz keyin izlash a[left:mid] qismida davom etadi. Shu turda izlash left

Func binarySearch(a []int,condidate int)

Int

{ left:=0

Right:=len(a)

For left

{

Mid:=(left+right)/2

If a[mid]==condidate

{

Return mid

}

If a[mid]

{

Left=mid

}

Else

{

Right=mid

}}

Return -1

}

Bu usul binar izlashning iterativ usili deyiladi, bu algoritmni rekursiya usilida ham yozish mumkin

Topshiriq: