在C中进行三元搜索

我想在C中对三进制进行三元搜索…我已经尝试过了……但是对于特定情况它并不适用。 请帮我删除以下程序中的错误 –

我的尝试：

#include #include 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(ka[m2]) return(tsearch(a,m2+1,j,k)); else return(tsearch(a,m1+1,m2-1,k)); } 

---

如果要搜索的数字出现在（arrays的）最后2-3个位置之一中，则它（仅）终止。 我犯了错误的地方???

Answer 1

中点计算错误。 你的方式，m1和m2不在i和j之间。

尝试

  m1 = i + (j - i) * 1 / 3; m2 = i + (j - i) * 2 / 3; 

Answer 2

@uncleo提出了一个很好的观点 – 并提供了一个不错的解决方案。

但更大的问题是，如果你搜索一个不在数组中的数字，就没有什么能阻止递归 – 它一直持续到崩溃为止。

而且， tsearch()的设计是可疑的; 显示的代码说它是一个void函数，但是你使用return(tsearch(...)); 几次（以及一些简单的return;陈述）。 当然，函数应该返回一个int和两个普通的return; 语句应该返回m1或m2 ？ 您还需要处理范围退化的情况（ i >= j ），这意味着该值不存在 – 也许您可以返回-1或类似的情况。

Answer 3

 #include int tsearch(int *a,int i,int j,int k); int main() { int a[10]={1,2,3,4,5,6,7,8,9,10}; int search; int k; printf("enter no to be searched :"); scanf("%d",&k); search=tsearch(a,0,9,k); printf("\n%d",search); return 0; } int tsearch(int *data, int left, int right, int value){ int i; int first,second; if(left>right) return -1; i= (right - left)/3; if(i==0) i++; first = i + left -1; second = i*2 + left - 1; if(data[first]==value) return first; else if(data[first]>value) return tsearch(data, left, first-1, value); else { if(data[second]==value) return second; else if(data[second]>value) return tsearch(data, first+1,second-1, value); else return tsearch(data, second+1,right, value); } } 

Answer 4

 int a[30],n,i; scanf("%d",&n); for(i=0;i 

这是典型的缓冲区溢出问题。 一旦知道n是什么，就动态分配内存。 uncleo很好地解决了你的问题。 🙂