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;
}

补充：软件开发 , C++ ,