斐波那契查找 野性酷女 2021-09-30 08:46 329阅读 0赞 # Introduce # 黄金分割查找,区别于插值查找找0.5,斐波那契查找找0.618。 ![18721752-80ed4220f6009617.png][] image.png # 原理介绍 # ![18721752-c539a5785ebbcbe8.png][] image.png 推导得出只要顺序数组长度=F\[k\]-1,就可将数组分为两部分,一部分长度F\[k-1\],一部分F\[k-2\] 此时mid=low+F\[k-1\]-1; 需要注意的是,顺序数组长度不一定=F\[k\]-1,所以需要对原数组扩容,让其满足该条件 ![18721752-d8f53f31211edd32.png][] 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; } } [18721752-80ed4220f6009617.png]: /images/20210918/3f105e6858d8487b807d5ce63b77c41d.png [18721752-c539a5785ebbcbe8.png]: /images/20210918/bd99c00c56a649f09c9371dd877b91ab.png [18721752-d8f53f31211edd32.png]: /images/20210918/690087d0b4db46e1a4adf1b1b72bf87a.png
还没有评论,来说两句吧...