Referat mavzu: Saralash algoritmlarining samaradorligi va qiyosiy tahlili. Bajardi: Omonboyev Rashidbek

3.Ikkilik daraxt boʻyicha qidirish
Maqsad qiymatni saralangan roʻyxatning oʻrtadagi qiymati bilan solishtirish uch xil natija berishi mumkin: qiymatlar teng, maqsad qiymati roʻyxat elementidan kichik va maqsad qiymati roʻyxat elementidan katta. Birinchi va eng yaxshi holda qidirish tugaydi. Qolgan ikki holda roʻyxat yarmini tashlab yuborishimiz mumkin.
Agar maqsad qiymati oʻrta elementdan kichik boʻlsa, u holda u bu oʻrta element oldida joylashgan boʻladi. Agar u oʻrta elementdan katta boʻlsa, u holda u oʻrta elementdan keyin joylashgan boʻladi. Bu roʻyxat yarmini tashlab yuborishga yetarlicha sabab boʻladi. Bu jarayonni takrorlab biz roʻyxatning qolgan qismlarini yarmini tashlab yuborishimiz mumkin. Natijada quyidagi algoritmga kelamiz:
BinarySearch(list,target,N)
list ko’rilayotgan ro’yxat
target maqsad qiymati
N ro’yxat eleamentlari soni
start=1
end=N
while start<=end do
middle=(start+end)/2
select(Compare(list[middle],target)) from
case -1: start=middle+1
case 0: return middle
case 1: end=middle-1
end select
end while
return 0
Bunda Compare(х,у) funksiyasi -1, 0 yoki 1 qiymatlarni mos holda xy shartlarda beradi. Algoritmlar tahlilida Compare funksiyani chaqirish bir solishtirish deb hisoblanadi.
Ushbu algoritmda agar maqsad qiymat topilgan oʻrta elementdan katta boʻlsa start oʻzgaruvchi middle qiymatidan 1 ga oshiqqa ta’minlanadi. Agar maqsad qiymat topilgan oʻrta elementdan katta boʻlsa end oʻzgaruvchi middle qiymatidan 1 ga kamga ta’minlanadi. Silijish 1 esa oʻrta element izlanayotgan qiymatga teng boʻlmagan hol bilan tushuntiriladi.
Sikl har doim toʻxtaydimi? Agar maqsad qiymat topilsa buni return operatori ta’minlaydi. Agar kerakli qiymat topilmasa, u holda har bir sikl iteratsiyasida yo start ning qiymati oshadi yo start oʻzgaruvchining qiymati kamayadi. Bu ularning qiymati bir biriga yaqinlashishini koʻrsatadi. Qandaydir vaziyatda ular tenglashadi va sikl start=end=middle da yana bir bor bajariladi. Bu oʻtishdan keyin (agar qidirilayotgan element ushbu indeksga mos kelmasa) yo start qiymati middle va end lardan 1 ga katta boʻladi, yo teskarisi, end oʻzgaruvchi middle va start lar qiymatidan 1 ga kam boʻladi. Ikki holatda ham sikl while yolgʻon boʻladi va sikl boshqa bajarilmaydi. Shu tufayli sikl har doim toʻxtaydi.
Algoritm har doim roʻyxatni yarimga boʻladi va biz tahlilda qandaydir k uchun N=2^k-1 deb faraz qilaylik. Agar shunday boʻlsa, ikkinchi oʻtishda nechta element qoladi? Uchinchidachi? Umuman olganda, tushunarliki, agar sikl qandaydir oʻtishda 2^j-1 element roʻyxat bilan ishlasa, u holda roʻyxatning birinchi yarmida 2^j-1-1 element boʻladi, bitta element oʻrtada va 2^j-1-1 elementlar roʻyxatning ikkinchi yarmida boʻladi. Shuning uchun keyingi oʻtishga 2^j-1-1 element qoladi(1