Как реализовать троичный поиск в C?
Возможный дубликат:
Троичный поиск в т
Напишите третичную [троичную] поисковую программу.
Примечания: Третичный поиск похож на бинарный поиск. В бинарном поиске мы рассматриваем две части массива и выбираем одну часть в качестве следующего пространства поиска. В третичном поиске мы рассматриваем массив в 3 равных частях. Для этого мы возьмем два "средних" индекса, middle1 и middle2 соответственно на 1/3 и 2/3 массива. Затем мы выбираем одну из 3 частей и продолжаем поиск в этом.
Кроме того, как найти временную сложность троичного поиска в худшем случае?
Моя попытка:
#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));
}
***
Он завершается, если искомый номер присутствует в одном из последних 2-3 мест (массива). Где я совершил ошибку?
1 ответ
Возможно, вы ищете Ternary Search?