Possible Duplicate:
Ternary search in C
编写三级[三元]搜索程序。
注意:三级搜索与二分搜索类似。在二分搜索中,我们考虑数组的两部分,并选择其中一部分作为下一个搜索空间。在三级搜索中,我们将数组分为 3 个相等的部分。为此,我们采用两个“中间”索引,分别位于数组的 1/3 和 2/3 处的 middle1 和 middle2。然后我们选择这 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 个位置之一,则终止。我哪里犯了错误?
最佳答案
关于c - 如何在C中实现三元搜索?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1347911/