Cでの3進検索の実装方法

Question

可能性の重複：
Ternary search in C

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

メモ：第3次検索はバイナリ検索と似ています。バイナリ検索では、配列の2つの部分を考慮し、次の検索スペースとして1つの部分を選択します。 3次探索では、アレイを3等分します。このために、配列の1/3と2/3にそれぞれ2つの中間インデックスmiddle1とmiddle2をとります。次に、3つのパーツの1つを選択し、検索を続けます。

また、最悪の場合、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のいずれかの場所に存在している場合は終了します。私はどこで間違いを犯したのですか？

Answer 1

おそらく、あなたはTernary Searchを探していますか？

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

Case Insensitive Ternary Search Tree