Introduce
黄金分割查找，区别于插值查找找0.5，斐波那契查找找0.618。
image.png
原理介绍
image.png
推导得出只要顺序数组长度=F[k]-1,就可将数组分为两部分，一部分长度F[k-1],一部分F[k-2]
此时mid=low+F[k-1]-1;
需要注意的是，顺序数组长度不一定=F[k]-1，所以需要对原数组扩容，让其满足该条件
image.png
code
package com.pl.arithmetic.search;
import java.util.Arrays;
/**
* <p>
*
* @Description: TODO
* </p>
* @ClassName FibonacciSearch
* @Author pl
* @Date 2020/12/30
* @Version V1.0.0
*/
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));// 0
}
/**
* 构建斐波那契数组
*
* @param
* @return int[]
* @exception
* @author silenter
* @date 2020/12/30 7:51
*/
public static int[] buildFibArr(){
int[] arr = new int[maxSize];
arr[0] = 1;
arr[1] = 2;
for (int i = 2; i < arr.length; i++) {
arr[i] = arr[i-1]+arr[i-2];
}
return arr;
}
/**
*斐波那契查找法
*
* @param oriArr
* @param target
* @return int
* @exception
* @author silenter
* @date 2020/12/30 7:51
*/
public static int fibSearch(int[] oriArr, int target) {
int arrLength = oriArr.length;
int[] fibArr = buildFibArr();
int fibIndex = 0;
//todo 寻找数组的长度接近的那个斐波那契元素，创造一个长度=fibArr[fibIndex]-1长度的数组,因为只有满足这个条件,才有mid = low + fibArr[fibIndex-1]-1
while (arrLength>fibArr[fibIndex]-1){
fibIndex++;
}
//数组长度不一定=fibArr[fibIndex]-1 所以需要扩容{1,8, 10, 89, 1000, 1234, 0, 0}
int[] fiboriArr = Arrays.copyOf(oriArr, fibArr[fibIndex]);
//因为数组为顺序数组，需要将0改成最大值
for (int i = arrLength; i < fiboriArr.length; i++) {
fiboriArr[i] = oriArr[arrLength-1];
}
//todo 在扩容数组中找值
int mid = 0;
int leftIndex = 0;
int rightIndex = oriArr.length-1;
//注意此时判断条件是原数组的边界比较，因为此时是在扩容数组中寻找，所以允许出现leftIndex = rightIndex，因为有一种情况，一直在右侧查找，有可能到扩容元素中查找
while (leftIndex<=rightIndex){
mid =leftIndex+fibArr[fibIndex-1] -1;
//向左查询
if (fiboriArr[mid]>target){
rightIndex = mid-1;
//此时将数组分为两部分 fibArr[fibIndex]-1(当前数组长度，即fiboriArr.length) = fibArr[fibIndex-1]-1(左部分长度)+fibArr[fibIndex-2]-1（右部分长度）+1（mid算一个长度）
//此时需要在左部分中查找target，此时左部分数组长度为 fibArr[fibIndex-1]-1 ，mid =fibArr[fibIndex-1-1]-1 所以fibIndex--
fibIndex--;
}else if (fiboriArr[mid]<target){
//此时将数组分为两部分 fibArr[fibIndex]-1(当前数组长度，即fiboriArr.length) = fibArr[fibIndex-1]-1(左部分长度)+fibArr[fibIndex-2]-1（右部分长度）+1（mid算一个长度）
//此时需要在右部分中查找target，此时右部分数组长度为 fibArr[fibIndex-2]-1 ，mid =fibArr[fibIndex-2-1]-1 所以fibIndex-=2
leftIndex = mid+1;
fibIndex-=2;
}else {
if (mid<arrLength){
return mid;
}else {
return arrLength-1;
}
}
}
return -1;
}
}
