在C中进行三元搜索

Question

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

我的尝试:

#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个位置之一中,它(仅)终止.我犯了错误的地方???

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？您还需要处理范围为degenerate(i >= j)的情况,这意味着该值不存在 - 也许您可以返回-1或类似的情况.