Fibonacci查找

一、Fibonacci查找方法是根據Fibonacci數列的特點對查找表進行分割。
        由算法知，Fibonacci查找在最壞情況下性能比折半查找差，Fibonacci查找的優點是分割時只需進行加、減運算。
Fibonacci數列的定義是：
        F(0)=0，F(1)=1，F(j)=F(j-1)+F(j-2) 。
 <SPAN style="FONT-SIZE: 24px">int fib(int n) 
{ 
   

 if (n==0) 
    { 
        return 0; 
    } 
    if (n==1) 
    { 
        return 1; 
    } 
    else  
    { 
        return fib(n-1)+fib(n-2); 
    } 
}</SPAN> 

int fib(int n)
{
 if (n==0)
 {
  return 0;
 }
 if (n==1)
 {
  return 1;
 }
 else
 {
  return fib(n-1)+fib(n-2);
 }
}

二、查找思想
        設查找表中的記錄數比某個Fibonacci數小1，即設n=F(j)-1。用Low、High和Mid表示待查找區間的下界、上界和分割位置，初值為Low=1，High=n。
⑴   取分割位置Mid：Mid=F(j-1) ；
⑵   比較分割位置記錄的關鍵字與給定的K值：
① 相等：查找成功；
②  大於：待查記錄在區間的前半段(區間長度為F(j-1)-1)，修改上界指針： High=Mid-1，轉⑴；
③  小於：待查記錄在區間的後半段(區間長度為F(j-2)-1)，修改下界指針：Low=Mid+1，轉⑴；
直到越界(Low>High)，查找失敗。
 

 <SPAN style="FONT-SIZE: 24px">int fib_search(int *a, int key, int num) 
{ 
    int low, high, mid;  
    low = 0; 
    high = fib(num)-2; 
    int k=num; 
 
    while(low <= high) 
    { 
        mid = low + fib(k-1) - 1;    
        if ( key < a[mid] ) 
        { 
            high = mid - 1; 
            k = k - 1; 
        } 
        else if ( key > a[mid] ) 
        { 
            low = mid + 1; 
            k = k - 2; 
        } 
        else 
        { 
            
              return mid; 
            
        } 
    } 
    return -1; 
} 
</SPAN> 

int fib_search(int *a, int key, int num)
{
    int low, high, mid; 
    low = 0;
    high = fib(num)-2;
    int k=num;

    while(low <= high)
    {
        mid = low + fib(k-1) - 1; 
        if ( key < a[mid] )
        {
            high = mid - 1;
            k = k - 1;
        }
        else if ( key > a[mid] )
        {
            low = mid + 1;
            k = k - 2;
        }
        else
        {
          
              return mid;
          
        }
    }
    return -1;
}