Write tertiary search program. Notes: Tertiary search is similar to binary search. In binary search we consider two parts of the array and select one part as the next search space. In tertiary search we consider the array in 3 equal parts. For this, we take two "middle" indices, middle1 and middle2 respectively at 1/3 and 2/3 of the array. Then we select one of the 3 parts and continue search in that. & also how to find time complexity of ternary search in worst case???
plz help me out....
my attempt:
#include<stdio.h>
#include<conio.h>
void tsearch(int *a,int i,int j,int k);
main() {
int a[30],n,i,k;
printf("\nEnter n:");
scanf("%d",&n);
printf("\nEnter nos in ascending order:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("Enter no to search:");
scanf("%d",&k);
tsearch(a,0,n-1,k);
getch();
}
void tsearch(int *a,int i,int j,int k) {
int m1,m2;
m1=(i+j)/3;
m2=2*(i+j)/3;
if(k==a[m1])
{
printf("\nno found at %d",m1);
return;
}
else if(k==a[m2])
{
printf("\nno found at %d",m2);
return;
}
if(k<a[m1])
return(tsearch(a,i,m1-1,k));
if(k>a[m2])
return(tsearch(a,m2+1,j,k));
else
return(tsearch(a,m1+1,m2-1,k));
}
***
it terminates if number to be searched is present in one of last 2-3 locations (of array)... plz...help me...where i have committed the mistake???