-5

可能重复：
C 中的三元搜索

编写三级[ternary]搜索程序。

注意：三级搜索类似于二分搜索。在二分搜索中，我们考虑数组的两个部分，并选择一个部分作为下一个搜索空间。在三次搜索中，我们将数组分为 3 个相等的部分。为此，我们分别在数组的 1/3 和 2/3 处采用两个“中间”索引，middle1 和 middle2。然后我们选择三个部分之一并继续搜索。

另外，在最坏的情况下如何找到三元搜索的时间复杂度？

我的尝试：

#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 个位置之一中，则它终止。我在哪里犯了错误？

4

1 回答 1

2

也许您正在寻找三元搜索？

http://en.wikipedia.org/wiki/Ternary_search

不区分大小写的三元搜索树

于 2009-08-28T16:07:11.743 回答