斐波那契数列

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：0、1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）。

黄金分割是指将整体一分为二，较大部分与整体部分的比值等于较小部分与较大部分的比值，其比值约为0.618。这个比例被公认为是最能引起美感的比例，因此被称为黄金分割。

斐波那契数列的两个相邻数的比例，无限接近黄金分割值0.618。

斐波那契查找

斐波那契查找算法类似于二分查找，也需要记录是有序的，仅改变了中间结点（mid）的位置。

思路

在斐波那契数列中找一个数F[k]，使 F[k]-1 恰好大于或等于 顺序表的长度n。
若顺序表长度n小于这个F[k]-1，则将原顺序表的长度n扩展为 F[k]-1，并向其扩展后尾部的空缺值填充原顺序表中最后一个元素的值。
mid不再是中间或插值得到，而是位于黄金分割点附近，即mid=low+F[k-1]-1（F代表斐波那契数列）

F[k]=F[k-1]+F[k-2]；由此可得（F[k]-1）=（F[k-1]-1）+（F[k-2]-1）+1 ，刚好分成三部分，这个1表示的就是mid的位置，这也是为什么将顺序表长度扩展为 F[k]-1。
将要查找的值value与arr[mid]相比

value = arr[mid]，mid位置的元素即为所要查找的值
value < arr[mid]，在中间记录的左半区继续查找，high=mid-1;k=k-1;
value > arr[mid]，在中间记录的右半区继续查找，low=mid+1;k=k-2;

代码

package com.nanzx.search;

import java.util.Arrays;

public class FibonacciSearch {
	public static int maxSize = 20;

	public static void main(String[] args) {
		int[] arr = { 1, 8, 10, 89, 1000, 1234 };
		System.out.println("查找元素的索引值index=" + fibSearch(arr, 1234));
	}

	public static int[] fib() {
		int[] fib = new int[maxSize];
		fib[0] = 1;
		fib[1] = 1;
		for (int i = 2; i < fib.length; i++) {
			fib[i] = fib[i - 1] + fib[i - 2];
		}
		return fib;
	}

	public static int fibSearch(int[] arr, int value) {
		int low = 0;
		int high = arr.length - 1;
		int mid = 0;
		int k = 0;
		int[] fib = fib();

		while (arr.length > fib[k]-1) {
			k++;
		}

		int[] temp = Arrays.copyOf(arr, fib[k]-1);
		for (int i = high + 1; i < temp.length; i++) {
			temp[i] = temp[high];
		}

		while (low <= high) {
			mid = low + fib[k-1] - 1;
			if (value < temp[mid]) {
				high = mid - 1;
				k--;
			} else if (value > temp[mid]) {
				low = mid + 1;
				k = k - 2;
			} else {
				if (mid < arr.length) {
					return mid;
				} else {
					return arr.length - 1;
				}
			}
		}
		return -1;
	}
}