//PROGRAM CODE 9.6
#include<iostream.h>
#include<conio.h>
#define max 30
void createIndex(int index[],int isize,int A[],int asize)
{
int i,j;
for(i=0,j=0;i<asize;i+=8,j++)
{
index[j]= A[i];
}
index[j] = A[asize-1];
}
int indexSeqSearch(int val, int index[], int isize, int A[], int asize)
{
int i=0,j=0,pos=0;
int high=0,low=0;
if(val > index[isize-1] && val < index[0])
return -1;
while(i<isize)
{
if(val == index[i])
{
pos = 8 * i; // here 8 is step size
return pos;
}
if(val < index[i])
{
low = 8 * (i-1);
high = 8 * i;
break;
}
else
{
low = 8 * i;
high = 8 * (i+1);
}
i++;
}
cout<<"\n low ="<<low<<"high"<<high;
while(low < high) // search in array from index low to high
{
if(val == A[low])
return low;
else
low++;
}
return -1;
}
int main()
{
int A[max]= {8,20,26,38,90,105,206,221,229,287,309,312,340,367,483,492,502,551,618,641,698,711,764,796};
int index[(max/8)+1]={0};
int position,t;
int key,i,choice;
int opt=0,pos=0;
clrscr();
cout<<"Enter number to be searched : ";
cin>>key;
t=(max/8)+1;
createIndex(&index[0],t,&A[0],max);
pos = indexSeqSearch(key, index,t,A,max);
if(pos != -1)
{
cout<<"\n\nFound at position "<< pos;
}
else
cout<<"\n\nNot found";
getch();
return 0;
}
/************** Output **************************
Enter number to be searched: 20
low = 0 high=8
20 found at position 1
Enter number to be searched: 711
low = 16 high=24
711 found at position 21
Enter number to be searched: 200
low = 0 high=8
200 not found
***************************************************/