黄金分割算法

Code_mzh

#include <iostream>
using namespace std;
typedef int Status;
int F[]={0,1,1,2,3,5,8,13,21,34,55,89};
Status Fibonaci_search(int a[],int n,int key){
    int left = 0;
    int right = n , mid , k = 0, i;
    ///while循环是用来找出K的数值，并且如果F【6】<n<F[7],则k等于7
    while( n > F[k] - 1)
    {
        k++;
    }
    ///下面是为了使a数组的长度等于F【k】,然后将后面新加的数组补全，并且等于都等于a[n]
    for(i = n; i < F[k] - 1; i++)
    {
        a[i] = a[n];
    }
    while(left <= right)
    {
        mid = left + F[k - 1] -1 ;///这是黄金分割的公式
        if( key == a[mid])
        {
            if(mid <= n)
            {
                return mid ;
            }else{
                return n;
            }

        }else if (key < a[mid])
        {
            right = mid - 1;
            k = k -1; ///前半部分的长度是F【k-1】
        }else if ( key > a[mid])
        {
            left = mid + 1;
            k = k - 2 ;///此处减2的原因是因为后半部分的长度是F【k-2】
        }
    }
    return 0;
}
int main() {
    int key ,n = 8;
    cout<<"输入要寻找的数值"<<endl;
    cin>>key;
    int a[n] = {1,3,5,6,7,9,12,24};
    int m = Fibonaci_search(a, n,key);
    if(m)
    {
        cout<<"查找成功"<<endl;
    }
    else{
        cout<<"查找不成功"<<endl;
    }
    return 0;
}