济南建站服务商/网络培训学校

二分查找

斐波那契查找

黄金分割，即将整体一分为二，较大部分与较小部分之比等于整体与较大部分之比，其比值约为1:0.618或1.618:1。

斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….，随着斐波那契数列的递增，前后两个数的比值会越来越接近0.618，利用这个特性，我们就可以将黄金比例运用到查找技术中。

#include <iostream>
#include <vector>
using namespace std;
const int MAX_SIZE = 20;int a[] = { 1, 5, 15, 22, 25, 31, 39, 42, 47, 49, 59, 68, 88 };//
void Fibonacci(int F[])
{F[0] = 0;F[1] = 1;for (size_t i = 2; i < MAX_SIZE; i++)F[i] = F[i - 1] + F[i - 2];}int FibonacciSearch(int value)
{int F[MAX_SIZE];Fibonacci(F);int n = sizeof(a) / sizeof(int); //13int k = 0;while (n > F[k] - 1) //k=8k++;vector<int> temp;temp.assign(a, a + n);for (size_t i = n; i < F[k] - 1; i++)temp.push_back(a[n - 1]);int l = 0, r = n - 1;while (l <= r){int mid = l + F[k - 1] - 1;if (temp[mid] < value) {l = mid + 1;k = k - 2;}else if (temp[mid] > value) {r = mid - 1;k = k - 1;}else {if (mid < n)return mid;elsereturn n - 1;}}return -1;
}
int main()
{int index = FibonacciSearch(47);cout << index << endl;}