6,-7-Mavzu: Ketma-ket qidiruv. Indeksli ketma-ket qidiruv. Ketma-ket qidiruvning samaradorligi Reja

Indeksli ketma-ket qidiruv
Mazkur ko’rinishdagi qidiruv amalga oshirilayotganda ikkita jadval tashkil qilinadi: o’z kalitiga ega ma’lumotlar jadvali (o’sish tartibida tartiblangan) va indekslar jadvali, bu ham ma’lumotlar kalitidan iborat-u, lekin kalitlar asosiy jadvaldan aniq bir integral orqali olingan.
Boshida berilgan argument bo’yicha ketma-ket qidiruv indekslar jadvalida amalga oshiriladi. Qachonki, biz berilgan kalitdan kichik kalitni aniqlaganimizda asosiy jadvalda qidiruvni quyi chegarasini o’rnatamiz – low, keyin esa yuqori chegarani - hi, ya’ni ( kind > key ).
Masalan, key = 101.
Qidiruv to’la jadval bo’yicha emas, balki low dan hi gacha davom etadi.

Indeksli ketma-ket qidiruv funksiyasi va dasturi (С++da)
#include
#include
int InSeqsearch(int realArray[], int N, int kind[2][1000],int m,int key, int *t)
{
int i=0,
low = 0,
hi = 0;
while ((i{
i++;
(*t)++;
}
(*t)++;
if (i==0)
low=0;
else
low=kind[1][i-1];
if (i==m)
hi=N;
else
hi=kind[1][i]-1;
for (int j=low; j<=hi; j++)
{
(*t)++;
if( key==realArray[j] )
{
return j;
}
}
return -1;
}
main ()
{
int i = 0 ,
N = 0,
mas[1000] = {0},
kind[2][1000] = {0},
key = 0,
P = 0,
index = 0,
kindIndex = 0,
t = 0;
cout<cin>>N;
cout<<"Massiv elementlarini kiriting!"<for (i=0; icin>>mas[i];
cout<<"Qidiruv elementini kiriting!"<cin>>key;
cout<<"Boshlangich qadamni kiriting! "<cin>>P;
i = P-1;
while(i{
kind[0][kindIndex] = mas[i];
kind[1][kindIndex++] = i;
i += P;
}
I ndex = InSeqsearch(mas,N,kind,kindIndex,key, &t);
if (index == -1)
cout<<"Bunday element massivda yuq "<< index <<" "<else
cout<<"Bunday element bor"<<" "<getch();
return 0;
}