11-Amaliy mashg’ulot: Izlash masalasi uchun algoritmlar va ularning murakkabliginq aniqlash

4. Indeksli ketma-ket qidiruvni samaradorligi
Agar boʻlishi mumkin barcha xolatlar teng extimolli deb olinsa, u holda qidiruv 
samaradorligini quyidagicha xisoblash mumkin: Belgilashlar kiritib olamiz: m – indeks 
oʻlchovi; m = n / p; p – qadam oʻlchovi Q = (m+1)/2 + (p+1)/2 = (n/p+1)/2 + (p+1)/2 = 
n/2p+p/2+1 (*) Q ni p boʻyicha differensiallab uni nolga tenglashtiramiz: dQ/dp=(d/dp) 
(n/2p+p/2+1)= - n / 2 p 2 + 1/2 = 0 
Bu yerdan p 2 =n ; n p opt 
Transpozisiya usuli
Ushbu usulda topilgan element roʻxatda bitta oldingi element bilan oʻrin almashtiriladi.
Agarda mazkur elementga koʻp murojaat qilinsa, bittadan oldinga surilib borib natijada 
roʻyxat boshida boʻladi.

---

Chizma. Qoʻshni elementlarni oʻrnini almashtirish r – ishchi koʻrsatkich q – 
ѐrdamchi koʻrsatkich, r dan bitta qadam orqada boʻladi s - ѐrdamchi koʻrsatkich, q dan ikkita 
qadam orqada boʻladi.
1-misol. 
Binar qidiruv usulidan foydalanib massiv elementlari orasida belgilangan elementni 
qidirish dasturi quyida keltirilgan:
1-usul. 
#include  
#include 
int Binsearch(int a[], int N, int key, int *t)
{
int l=0, r=N-1, mid=(l+r)/2;
while (l<=r)
{ *t+=1;
if (a[mid]==key) return mid;
if (a[mid]>key) r=mid-1;
else l=mid+1;
mid=(l+r)/2;
}
a[N]=key;
return N;
} main () 
{ 
int i, N, mas[1000], key, P, t=0;
cout<cin>>N;
cout<<"Massiv elementlarini kiriting!"<for (i=0; icin>>mas[i];
cout<<"Qidiruv elementini kiriting!"<cin>>key;
P=Binsearch(mas,N,key, &t);
if (P==N) cout<<"Bunday elementni massivga qoʻshis lozim"<<"
"<
"<
getch();
return 0;
}