-5

重複の可能性:
C の三分探索

三次[三次]検索プログラムを書きます。

注: 三次検索は二分検索に似ています。二分探索では、配列の 2 つの部分を考慮し、次の検索空間として 1 つの部分を選択します。三次探索では、配列を 3 つの等しい部分で検討します。このために、配列の 1/3 と 2/3 でそれぞれ middle1 と middle2 という 2 つの "中間" インデックスを取得します。次に、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 か所のいずれかに存在する場合、終了します。どこで間違いを犯したのですか？

4

1 に答える 1

2

三分探索をお探しですか？

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

大文字と小文字を区別しない三項探索木

于 2009-08-28T16:07:11.743 に答える