如何在C中實現三元搜索？

Question

可能重複：
Ternary search in C

收件叔[三元]搜索程序。

注：第三級搜索類似於二分查找。在二分查找中，我們考慮數組的兩個部分，並選擇一個部分作爲下一個搜索空間。在三級搜索中，我們考慮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的位置中的一個。我犯了什麼錯誤？

Answer 1

也許您在尋找Ternary Search？

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

Case Insensitive Ternary Search Tree