精华内容
下载资源
问答
  • 1,斐波拉契查找基本介绍 黄金分割点:是把一条线段分为两部分,使得一部分与全程之比等于另一部分跟这部分之比,比例近似于0.618,称为黄金分割点 斐波那契数列{1, 1, 2, 3, 5, 8 ... n, m, m + n}发现两个相邻数...

    1,斐波拉契查找基本介绍

    • 黄金分割点:是把一条线段分为两部分,使得一部分与全程之比等于另一部分跟这部分之比,比例近似于0.618,称为黄金分割点
    • 斐波那契数列{1, 1, 2, 3, 5, 8 ... n, m, m + n}发现两个相邻数的比例,无限接近于0.618
    • 斐波那契查找,依旧基于数组是有序数组,并使数组长度与斐波那契数组元素相匹配,之后类似于二分查找方式,以斐波那契数组的数组特性f[k] = f[k - 1] + f[k - 2],对目标数组取中值middle = low+ f[k - 1] - 1后再进行分段查找
      在这里插入图片描述
    • 与二分查找和插值相比,重点依旧是取中值部分求值方式不同;另外效果与二分查找基本一致,网上有分析称斐波那契查找是加减运算,速度会高于二分查找
    • 斐波拉契查找流程分析
      • 首先初始化一个斐波拉契数组,数组长度可以初始化为20,尽量支持扩容
      • 用原数组长度去匹配到斐波拉契数组的元素值,获取到f[k] - 1 < array.length最近的数据作为原始数组在斐波拉契查找法中的真实长度,具体可参考示意图
      • 对原数组进行拷贝,拷贝目标数组的长度为f[k] - 1,并将多与原数组长度的新加数组部分数据值修改为原数组最大值,此时数组构建完成,可以开始查找
      • 斐波拉契查找中值公式:middle = low + f[k - 1] - 1;其中low表示左侧最小索引,f[k - 1] - 1表示middle值的左侧数组长度
      • 公式推导如下:数组长度 f[k] - 1 = f[k - 1] + f[k - 2] - 1,即f[k] - 1 = f[k - 1] - 1 + 1 + f[k - 2] - 1;此时可以将f[k - 1] - 1理解为数组中值的左侧部分数组,f[k - 2] - 1理解为数组中值的右侧部分数组,中间的1即表示middle索引部分,也就是中值数据
      • 获取到中值索引后,对中值数据与查找数据进行比对,如果小于该数据,则向左查找;如果大于该数据,则向右查找;如果相等,则根据当前中值索引是否大于原数组的最大索引判断返回当前索引还是最大索引
      • 向左查找:此时中值数据左侧数组部分长度为f[k - 1] - 1,继续推导公式f[k - 1] - 1 = f[k - 2] - 1 + 1 + f[K - 3] - 1,以f[k - 1] - 1继续为完整数组来看,则中值的左侧部分应该为f[k - 2] - 1,即f[k - 1 - 1] - 1,进入下一轮循环,此时k--
      • 向右查找:同上一步,中值的右侧部分应该为f[k - 3] - 1,即f[k - 2 - 1] - 1,此时k -= 2

    2,斐波拉契查找原理示意图

    • 初始化数组:int[] array = {1, 2, 3, 4, 5, 6};
    • 初始化斐波拉契数组:int[] fbl = {1, 1, 2, 3, 5, 8};
    • 拷贝原数组后:array = {1, 2, 3, 4, 5, 6, 6},(array.length = fbl[k] - 1), 数组长度为fbl[k] - 1,此时k=5,则array长度应该为7
    • 则数组的的各部分组成如下
      在这里插入图片描述
    • 此时查找数据,如果落于middle左侧,则k--;落于middle右侧,则k-=2

    3,代码实现

    package com.self.datastructure.search;
    
    import java.util.Arrays;
    
    /**
     * 斐波拉契查找法
     *
     * @author pj_zhang
     * @create 2020-03-14 21:50
     **/
    public class FibratcheSearch {
    
        public static void main(String[] args) {
            int[] array = {1, 12, 23, 34, 55, 78, 156, 765, 873, 987};
            System.out.println(fibratcheSearch(array, 874));
        }
    
        /**
         * 斐波拉契查找流程
         * * 先初始一个长度为20的斐波拉契数组备用, 数组长度如果超过fbl[19], 可以进行扩容
         * * 用数组长度去匹配合适的斐波拉契数值值, 作为原始数组斐波拉契查找法中的真实长度
         * * 对原始数组进行拷贝, 拷贝后的长度 = (斐波拉契的数值值 - 1), 多余原始数组部分初始化为0
         * * 对多余部分初始化为0进行修改, 修改为数组的最大值, 保证数组有序
         * * 数据初始化完成后, 继续进行数据查询, 数据查找与二分法基本一致, 只是middle的取值方式不一致
         * * 斐波拉契查找中: middle = left + F[k - 1] - 1;
         * * 其中F数组表示斐波拉契数组, k表示数据匹配到的斐波拉契数组下标, k对应长度即原始数组拷贝后的长度
         * * 根据斐波拉契查找算法补全位后, 原数组长度为 f[k] - 1
         * * 因为 f[k] = f[k - 1] + f[k - 2]
         * * 所以 f[k] - 1 = f[k - 1] + f[k - 2] - 1
         * * 即 f[k] - 1 = f[k - 1] - 1 + 1 + f[k - 2] - 1
         * * f[k - 1] - 1: 表示middle左侧数组长度
         * * 1: 表示middle所在位置
         * * f[k - 2] - 1: 表示middle右侧数组长度
         *
         * @param array 原数组
         * @param target 需要查找的值
         * @return 返回索引
         */
        public static int fibratcheSearch(int[] array, int target) {
            int left = 0; // 左索引
            int right = array.length - 1; // 右索引
            // 数组长度匹配到的斐波拉契数组下标
            // 该下标对应值为拷贝后的数组长度
            int k = 0;
            // 初始化斐波拉契数组
            int[] fbl = initFbl(20);
            // 用数组长度匹配到斐波拉契数组的对应元素, 比如数组长度为7, 则匹配8; 为10, 匹配13; 依次类推
            // 简单斐波拉契数据: {1, 1, 2, 3, 5, 8, 13, 21}, 即从1开始, 后一个数为前两个数之和
            for (;fbl[k] - 1 < array.length;) {
                // 这部分可以添加扩容逻辑,
                // 20表示初始化长度, 如果k为20依旧小于, 则进行扩容,
                // 扩容可以以array长度进行算法匹配, 求出大概索引位置进行扩容
                // 也可以类似于集合扩容, 进行1.5或者2倍扩容
                k++;
            }
            // 拷贝原数组为斐波拉契查找需要的长度
            int[] temp = Arrays.copyOf(array, fbl[k] - 1);
            // 数组长度增加后, 增加部分数据值初始化为0, 修改值统一为最大值, 保证数组有序
            for (int i = right + 1; i < temp.length; i++) {
                temp[i] = temp[right];
            }
    
            // 原数组和斐波拉契数组全部初始化完成后, 可以进行数据查找
            // 获取到middle值: middle = left + F[k - 1] - 1;
            for (;left <= right;) {
                // fbl[k]表示当前数组的长度, 如果已经循环多次, 依旧表示查找区间的数组长度
                // 例: 数组长度为13, fbl[k]=13, k=6, left=0, 则middle=7,
                //     此时向左继续查找, 则right=6, k=5, fbl[k]=7;
                // 对于斐波拉契查找法, 中值索引的选择就是以斐波拉契数组的前一个数为基本参考
                // 因此, 此时 midlle 取值就是以fbl[k - 1]作为基本参考
                // 以斐波拉契数组的组成方式,
                //  * middle左侧的数组长度是fbl[k - 1] - 1, 中值索引参考为fbl[k - 1 - 1]
                //  * middle右侧的数组长度是fbl[k - 2] - 1, 中值索引参考为fbl[k - 2 - 1]
                int middle = left + fbl[k - 1] - 1;
                if (temp[middle] > target) { // 向左继续找
                    // 如果中值索引对应值小于目标值, 则向左侧继续寻找
                    // 此时右侧索引变成中值索引的左侧索引
                    right = middle - 1;
                    // 当前循环没有匹配到, 且匹配到左侧, 需要进行下一轮循环继续匹配
                    // 则下一轮循环的middle就是以fbl[k - 1]为完整数据进行求中值处理
                    // 则对于左侧 middle 的参考系为fbl[k - 1 - 1]
                    // 所以此时k应该减1
                    k--;
                } else if (temp[middle] < target) { // 向右继续找
                    // 如果中值索引对应值大于目标值, 则向侧继续寻找
                    // 此时左侧索引变为中值索引的右侧索引
                    left = middle + 1;
                    // 当前没有匹配到, 且匹配到右侧, 需要进行下一轮循环匹配
                    // 此时右侧数组的长度为fbl[k - 2]
                    // 对于右侧数组来说, 中值索引参考应为fbl[k - 2]的前一个数即fbl[k - 1 - 2]
                    // 此时k应该减2
                    k -= 2;
                } else { // 相等, 返回索引
                    return middle > right ? right : middle;
                }
            }
            return -1;
        }
    
        /**
         * 初始化斐波拉契数组
         *
         * @return
         */
        private static int[] initFbl(int size) {
            int[] array = new int[size];
            array[0] = 1;
            array[1] = 1;
            for (int i = 2; i < size; i++) {
                array[i] = array[i - 1] + array[i - 2];
            }
            return array;
        }
    
    }
    
    展开全文
  • 这篇文章将解析二分查找、插值查找、斐波拉契查找,这三种查找算法其实都类似,只是优化了分段的方式 插值查找、斐波拉契查找是二分查找的优化 二分查找 二分查找:顾名思义,要将查找的线性表分成两段 用给定值k...

    查找算法

    经典的查找算法有7种:
    顺序查找,二分查找,插值查找,斐波那契查找,树表查找,分块查找,哈希查找

    其中顺序查找没得说,就是简单的按照顺序从前往后查,一个for循环就解决了

    这篇文章将解析二分查找、插值查找、斐波拉契查找,这三种查找算法其实都类似,只是优化了分段的方式

    插值查找、斐波拉契查找是二分查找的优化


    二分查找

    二分查找算法概念

    二分查找:顾名思义,要将查找的线性表分成两个线性表

    用给定值k先与中间结点的关键字比较,中间结点把线形表分成两个子表,若相等则查找成功;若不相等,再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表,这样递归进行,直到查找到或查找结束发现表中没有这样的结点

    注意:二分查找需要线性表有序

    例如:一个数组1,8,10,89,1000,20003,二分查找的步骤:

    • 设置左指针left指向1(线性表最左边),右指针right指向20003(线性表最右边),传入查找值,例如1000
    • 计算中间值mid = (left + right) / 2,也就是2,指向10
      在这里插入图片描述
    • 将线性表分为左右两段及中间值,判断查找值1000是大于、小于、等于中间值
    • 现在大于中间值,即向右查找,递归上面的方法(移动指针)
      在这里插入图片描述
    • 继续判断中间值与查找值,现在是等于,即找到了

    Java实现二分查找

    按照上面的步骤:

    public class BinarySearch {
    
        public static void main(String[] args) {
            int[] arr = {1,8,10,89,1000,20003};
    
    	    int index = binarySearch(arr,0,arr.length - 1,1000);
            System.out.println("index = "+ index);
        }
    
        /**
         * @param arr 要查找的数组
         * @param left 左指针:指向查找的数组最左边
         * @param right 右指针:指向查找的数组的最右边
         * @param findVal 要查找的值
         * @return 找到就返回下标,否则返回-1
         */
        public static int binarySearch(int[] arr,int left,int right,int findVal){
            num++;
            //当left > right 时,递归了整个数组,没有找到
            if (left > right){
                return -1;
            }
            //中间指针
            int mid = (left + right) / 2;
            int midVal = arr[mid];
            //如果找的值大于中间值,向右递归
            if (findVal > midVal){
                return binarySearch(arr,mid + 1,right,findVal);
            }
            //小于,向左递归
            else if (findVal < midVal){
                return binarySearch(arr,left,mid - 1,findVal);
            }
            else {
                return mid;
            }
    
        }
    }    
    

    得到结果:

    在这里插入图片描述

    但实际上还有点可以优化,当有多个相同的数时,被查找只能得到一个数

    如:1,8,10,89,1000,1000,1000,20003,查找到第5个数10000就结束了,现在想返回所有数的集合

    思路:当查找到要求的数时,先向左右查找,看是否存在相等的数,直到到达数组边界、找到不相等的数为止

       public static List binarySearchList(int[] arr, int left, int right, int findVal){
    
            //当left > right 时,递归了整个数组,没有找到
            if (left > right){
                return new ArrayList();
            }
            //中间指针
            int mid = (left + right) / 2;
            int midVal = arr[mid];
            //如果找的值大于中间值,向右递归
            if (findVal > midVal){
                return binarySearchList(arr,mid + 1,right,findVal);
            }
            //小于,向左递归
            else if (findVal < midVal){
                return binarySearchList(arr,left,mid - 1,findVal);
            }
            else {
    
                List<Integer> list = new ArrayList<>();
    
                //当找到值arr[mid]时,判断左右两边是否有相同的值
    
                //mid左
                int temp = mid - 1;
    
                while (true){
                    //当temp为最左边或者arr[temp] 不是要找的值
                    if (temp < 0 || arr[temp] != findVal){
                        break;
                    }
                    list.add(temp);
                    temp --;
                }
                //加入mid
                list.add(mid);
                //mid右
                temp = mid + 1;
    
                while (true){
                    //当temp为最左边或者arr[temp] 不是要找的值
                    if (temp > arr.length - 1 || arr[temp] != findVal){
                        break;
                    }
                    list.add(temp);
                    temp++;
                }
    
                return list;
            }
    
        }
    

    查询:

        public static void main(String[] args) {
            int[] arr = {1,8,10,89,1000,1000,1000,20003};
    
            List list = binarySearchList(arr,0,arr.length -1,1000);
            System.out.println("list = "+ list);
    
        }
    

    在这里插入图片描述

    非递归二分查找

    前面使用递归实现了二分查找,这里用非递归法(循环)

     /**
         *
         * @param arr 查找数组
         * @param targert 待查找的数
         * @return 返回对应下标,-1表示没找到
         */
        public static int binarySearch(int[] arr,int targert){
    
            int left = 0;
            int right = arr.length -1;
    
            while (left <= right){
                int mid = (left + right) / 2;
                if (arr[mid] == targert){
                    return mid;
                }
                //待查找的数在数组左边
                else if (arr[mid] > targert){
                    //右指针移动到中点
                    right = mid -1;
                }
                //待查找的数在数组右边
                else {
                    //左指针移动
                    left = mid + 1;
                }
            }
            return -1;
        }
    

    测试:

        public static void main(String[] args) {
            int[] arr = {1,8,10,89,1000,20003};
            int index = binarySearch(arr,1);
    
            System.out.println("查找的数下标为 :"+index);
        }
    

    在这里插入图片描述


    插值查找

    插值查找算法的概念

    当一个数组很长,且要查找的数在比较前或者比较后的位置,就需要多次二分,如果我们知道该值大概在什么位置就不需要查询多次,类似与字典查找时可以根据索引找到索引a开头的单词

    二分查找仅是简单的按照数组的大小进行划分,插值查找是根据查找关键字与查找表中最大最小记录关键字比较后的查找方法

    将二分查找的mid改为
    mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left])

    明显,插值查找也需要数组是有序的

    例如:一个大小为100的数组,值对应为1~100
    现需要查找1

    • 当使用二分查找,mid分别为49,24,11,5,2,0
    • 当使用插值查找,mid为0,直接查询到了
      mid= 0 + (99-0)*(1-1)/(100-0)=0

    Java实现插值查找

    插值查找除了mid计算不同,其他都与二分查找相同

    package com.company.search;
    
    /**
     * 插值查找算法
     */
    public class InsertValSearch {
    
        public static void main(String[] args) {
            int[] arr = new int[100];
            for (int i = 0;i < 100;i++){
                arr[i] = i+1;
            }
    
            int i = insertValSearch(arr, 0, arr.length - 1, 1);
            System.out.println("index = "+i);
        }
    
        //插值查找算法
    
        /**
         * @param arr 数组
         * @param left 左边索引
         * @param right 右边索引
         * @param findVal 查找值
         * @return 找到就返回对应的下标,否则-1
         */
        public static int insertValSearch(int[] arr,int left,int right,int findVal){
            //退出
            if (left > right || findVal < arr[0] || findVal > arr[arr.length-1]){
                return -1;
            }
            //求出mid
            int mid = left + (right - left) * (findVal - arr[left]) / (arr[right] - arr[left]);
            int midValue = arr[mid];
    
            //如果大于中间值,向右递归
            if (findVal > midValue){
                return insertValSearch(arr,mid + 1,right,findVal);
            }
            //如果小于中间值,向左递归
            else if (findVal < midValue){
                return  insertValSearch(arr,left,mid - 1,findVal);
            }
    
            else {
                return mid;
            }
    
    
        }
    }
    

    在这里插入图片描述


    斐波拉契查找

    斐波拉契查找算法的概念

    斐波拉契查找算法与黄金比例、斐波拉契数列有关

    斐波拉契数列f(n) = f(n - 1) + f(n - 2),最开始两个数为1的数列,叫斐波拉契数列
    10位斐波拉契数列:[1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

    黄金分割:是指事物各部分间一定的数学比例关系,即将整体一分为二,较大部分与较小部分之比等于整体与较大部分之比,其比值约为1:0.618或1.618:1,0.618被公认为最具有审美意义的比例数字

    斐波拉契数列中,两个相邻的数,小值除大值就会靠近黄金比例,如2/3=0.667,3/5=0.6 … 34/55=0.6181

    斐波拉契查找

    • 斐波拉契查找和前两种相似,也是改变mid值,mid位于黄金分割点附近
      mid = low + f(k-1) - 1

    • 就是根据数组的大小选择斐波拉契数列(如果数组大小不等于数列的值,填充值到大小等于最近的数列值),将数组分割成两个数组,例如数组大小为10,就将原数组填充值为大小13的数组,根据数列划分为5,8大小的数组

    • 斐波那契查找也是二分查找的一种提升算法,通过运用黄金比例的概念在数列中选择查找点进行查找,提高查找效率。同样地,斐波那契查找也属于一种有序查找算法

    例如:数组1,6,8,10,88,1000,3456,查找1

    • 数组大小为7,在最后填充一个值1,6,8,10,88,1000,3456,3456,数组大小为8,根据数列划分为两个数组:1,6,8,10,881000,3456,3456,这个时候k=5
      mid = low + f(k-1) - 1 = 0 + f(4) - 1 = 4,arr[mid]=88

    在这里插入图片描述

    • 按照二分查找,判断arr[mid]与查找的值的大小,小于即继续向左查找,1,6,8,10,88划分为1,6,810,88

    在这里插入图片描述

    • 继续向左查找,明显6>1
      在这里插入图片描述

    • 继续向左查找,mid=0+1-1=0,arr[mid]=1找到了值,结束

    在这里插入图片描述

    Java实现斐波拉契查找算法

    首先,需要算出斐波拉契数列,然后根据斐波拉契数列划分数组,查找值

    package com.company.search;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    
    /**
     * @author zfk
     * 斐波那契查找算法
     */
    public class FibonacciSearch {
        //斐波拉契数列大小
        private  static int maxSize = 20;
        //查找次数
        static int num = 0;
        public static void main(String[] args) {
            int[] arr = {1,6,8,10,88,1000,3456};
            System.out.println("index = "+fibSearch(arr,1));
            System.out.println("查找次数:"+num);
        }
    
        /**
         * @return 返回斐波拉契数列
         */
        public static int[] fib(){
            int[] f = new int[maxSize];
    
            f[0] = 1;
            f[1] = 1;
    
            for (int i = 2;i < maxSize;i++){
                f[i] = f[i - 1] + f[i - 2];
            }
            return f;
        }
    
        /**
         * @param arr 查找的数组
         * @param key 查找的数
         * @return 返回对应的下标,没有为-1
         */
        //斐波拉契查找算法
        public static int fibSearch(int[] arr,int key){
    
            int low = 0;
            int high = arr.length - 1;
            //斐波拉契要分割的数值的下标
            int k = 0;
            //存放mid值
            int mid = 0;
            //获取斐波拉契数列
            int[] f = fib();
            //获取斐波拉契数列的分割点的下标
            while (high > f[k] - 1){
                k++;
            }
            //因为f[k]可能大于数组arr,需要构造一个新的数组
            int[] temp = Arrays.copyOf(arr,f[k]);
            //补齐temp,可以使用arr数组最后的数填充temp后面的0
            for (int i = high + 1;i < temp.length;i++){
                temp[i] = arr[high];
            }
            //找到key
            while (low <= high){
                num++;
                mid = low + f[k-1] -1;
                //继续向数组的左边查找
                if (key < temp[mid]){
                    high = mid - 1;
                    //下一步斐波拉契数列为f[k-1-1]
                    k--;
                }
                //向数组的右边找
                else if (key > temp[mid]){
                    low = mid + 1;
                    //f[k] = f[k-1] + f[k-2] ,后面为f[k-2]相差的位置为2
                    k -= 2;
                }
                else {
                    //找到,返回小的下标
                    return Math.min(mid,high);
                }
            }
            //没有找到
            return  -1;
    
    
        }
    }
    
    

    在这里插入图片描述


    总结

    这里介绍了4中查找算法

    当数组无序时,只能用顺序查找从头开始找
    当数组有序时,可以选择这3种有序查找:

    • 二分查找:根据mid值均分数组,比较arr[mid]与查找值,不相等就继续递归划分查找
    • 插值查找:在二分查找的基础上优化,mid=low+(right-left)*(findVal-arr[left])/(arr[right]-arr[left]),这样划分数组时可以根据查找值与数组最大最小值的比例有效划分数组
    • 斐波拉契查找:与上面两种相似,根据斐波拉契数列划分数组

    在不同的情况下,二分查找、插值查找、斐波拉契查找效率不同

    有7种查找算法,树表查找,分块查找,哈希查找后续实现

    展开全文
  • * 思路: 1.首先判断目标值边界,在左或右端点上就直接输出索引,在小于左端点或大于右端点即为越界输出-1 * 2.分别设置左节点(0.318倍的步长)和右节点(0.682倍的步长) * 3....* -接着判断左节点和右节点是否相等...

    自己想的思路,随便试验了下好像能行,不知道有么有错误

    * 思路:
         1.首先判断目标值边界
            在左或右端点上就直接输出索引,在小于左端点或大于右端点即为越界输出-1
    *      2.分别设置左节点(0.318倍的步长)和右节点(0.682倍的步长)
    *          3.1.循环的边界条件a.
    *             -接着判断左节点和右节点是否相等
                    如果相等证明:要么是右端点和左端点相差为1,要么是相差为3!!!!
    *           ps:此判断属于特殊处理是解题的关键点
                    相差为3时需要移动右节点以保证能判断此区间内的全部值(端点已在第一部判断)
    *               相差为1时其实属于判断两个端点,属于重复判断(无伤大雅)
                    如果没有值满足则必然target不存在了
    *          3.2.循环的边界条件b.
    *              -落在左节点和右节点上的幸运儿,此时满足程序结束直接输出
    *               4.循环的设置
    *                 a.如果小值都大于目标值,则所求值在小值左边
    *                 b.如果大值都小于target,则在大值右边
    *                 c.不在小值左边也不在大值右边就是在中间了

    重点需要理解的是第三步:特别注意特殊情况 right - left = 3时,此时两个节点是一样大的,所以需要对右节点加一,以保证区间内的值能全部判断到,比如程序进行了多次循环后进入区间【0,3,5,7】,这时pivot1 = pivot2 = left+1,左右端点已经在第一步判断完,但是这时程序判断不到left+2位置上的5,所以需要给大节点pivot1加上1得到left+2这个index判断即可。

    package com.mytest.datastructures.search;
    
    /**
     * @author : zhanghj
     */
    public class MyFibSearch {
        //这是一个main方法,是程序的入口:
        public static void main(String[] args) {
            int[] arr = new int[100];
            for (int i = 0; i < 100; i++) {
                arr[i] = i;
            }
            System.out.println(FibSearch(arr, 0, arr.length - 1, 11));
        }
    
        /*
        * 思路: 1.首先判断目标值边界,在左或右端点上就直接输出索引,在小于左端点或大于右端点即为越界输出-1
         *      2.分别设置左节点(0.318倍的步长)和右节点(0.682倍的步长)
    *           3.循环的边界条件a.
    *               -接着判断左节点和右节点是否相等,如果相等证明:要么是右端点和左端点相差为1,要么是相差为3!!!!
    *           ps:此判断属于特殊处理是解题的关键点,相差为3时需要移动右节点以保证能判断此区间内的全部值(端点已在第一部判断)
    *               相差为1时其实属于判断两个端点,属于重复判断(无伤大雅),如果没有值满足则必然target不存在了
    *             循环的边界条件b.
    *              -落在左节点和右节点上的幸运儿,此时满足程序结束直接输出
    *           4.循环的设置
    *             a.如果小值都大于目标值,则所求值在小值左边
    *             b.如果大值都小于target,则在大值右边
    *             c.不在小值左边也不在大值右边就是在中间了
        * 
        * */
    
        public static int FibSearch(int[] arr, int left, int right, int target) {
            System.out.println("hello");
            if (left < right) {
                //1.首先上来就判断一次目标值边界
                //记录左右值
                int l = left;
                int r = right;
                //左右值满足直接返回
                if (arr[l] == target) {
                    return l;
                }
                if (arr[r] == target) {
                    return r;
                }
                //左右值超出直接错误
                if(target< arr[l]||target>arr[r]){
                    return -1;
                }
                //2.分别设置左节点和右节点
                int pivot1 = (int) ((r - l) * 0.618) + left;
                int pivot2 = (int) ((r - l) * 0.382) + left;
                //3.循环的边界条件
                if(pivot1 == pivot2){
                    pivot1++;
                    if(arr[pivot1]!= target && arr[pivot2]!= target){
                        return -1;
                    }
                }
                if (arr[pivot1] == target) {
                    return pivot1;
                }
                if (arr[pivot2] == target) {
                    return pivot2;
                }
                //4.循环的设置
                //如果小值都大于目标值,则所求值在小值左边
                if (arr[pivot2] > target) {
                    return FibSearch(arr, l, pivot2, target);
                } else if (arr[pivot1] < target) {//如果大值都小于target,则在大值右边
                    return FibSearch(arr, pivot1, r, target);
                }//不在小值左边也不在大值右边就是在中间了
                return FibSearch(arr, pivot2, pivot1, target);
            }else {
                return -1;
            }
        }
    }
    
    

    展开全文
  • 斐波拉契查找算法基本介绍 算法原理 代码实现: public class 斐波拉契查找 { final static int maxSize = 20; public static void main(String args[]) { // 数组需要排序 int a[] = {1, 8, 10, 89, ...

    学习数据结构和算法的日常Demo

    斐波拉契查找算法基本介绍

    在这里插入图片描述

    算法原理

    在这里插入图片描述
    在这里插入图片描述

    代码实现:

    public class 斐波拉契查找 {
        final static int maxSize = 20;
    
        public static void main(String args[]) {
            // 数组需要排序
            int a[] = {1, 8, 10, 89, 1000, 1234};
            int i = fibSearch(a, 10);
            if (i == -1) {
                System.out.println("没有找到!");
            } else {
                System.out.println("下标:" + i);
            }
        }
    
        // 得到一个斐波拉契数列数列
        public static int[] fib() {
            int[] f = new int[maxSize];
            f[0] = 1;
            f[1] = 1;
            for (int i = 2; i < maxSize; i++) {
                f[i] = f[i - 1] + f[i - 2];
            }
            return f;
        }
    
        public static int fibSearch(int[] a, int value) {
            int low = 0;
            int high = a.length - 1;
            int mid = 0;
            int k = 0;  // 表示斐波拉契分割数值的下标
            int f[] = fib();    // 获取斐波拉契数列
            // 获取到斐波拉契分割数值的下标
            while (high > f[k] - 1) {
                k++;
            }
            // 因为f[k]可能大于数组a长度,因此需要使用Arrays类,扩容
            // 扩加部分用0填充
            int[] temp = Arrays.copyOf(a, f[k]);
            // 但我们使用a[a.length-1]填充:
            // a[] = {1, 8, 10, 89, 1000, 1234,0,0,0} -> {1, 8, 10, 89, 1000, 1234,1234,1234,1234}
            // 从a.length索引开始填充
            for (int i = high + 1; i < temp.length; i++) {
                temp[i] = a[high];
            }
            // 循环处理,找到数value
            while (low <= high) {
                mid = low + f[k - 1] - 1;
                if (value < temp[mid]) {
                    // 应该继续向左边查找
                    high = mid - 1;
                    // 说明k--
                    // f[k] = f[k-1] + f[k-2]
                    // 因为前面有f[k-1],所以可以继续拆分f[k-1] = f[k-2] + f[k-3]
                    // 即下次循环mid = f[k-1-1] - 1
                    k--;
                } else if (value > temp[mid]) {
                    // 应该继续向右边查找
                    low = mid + 1;
                    // 说明k -= 2
                    // f[k] = f[k-1] + f[k-2]
                    // 因为后面有f[k-2] 所以继续拆分f[k-1] = f[k-3] + f[k-4]
                    // 即在f[k-2]前面继续查找k-=2
                    // 即下次循环mid = f[k-1-2] - 1
                    k -= 2;
                } else {
                    if (mid <= high) {
                        return mid;
                    } else {
                        return high;
                    }
                }
            }
            return -1;
        }
    }
    
    

    在这里插入图片描述

    GitHub:数据结构和算法源代码

    展开全文
  • } /** * 斐波那契查找算法 * @param arr * @param value * @return */ public static int fibonacciSearch(int[] arr, int value) { //查找界限 int low = 0; int high = arr.length - 1; //存放分割数的下标和值 ...
  • 1、什么是斐波那契数列? 1、1、2、3、5、8、13、21、34…… 斐波那契数列又被成为黄金分割数列,因为 前一项/后一项越来越趋近于0.618 由上面的数列,可以发现 除了前两项,后面每一...斐波那契查找原理与前两种相...
  • 斐波那契查找算法又称为黄金分割法查找算法,是一种有序查找算法。 斐波那契数列,又称黄金分割数列,指的是这样一个数列:1、1、2、3、5、8、13、21、····。在数学上,斐波那契被递归方法如下定义:F(1)=1,F(2...
  • Java基础查找算法(4)——斐波那契查找 1.斐波那契查找简述 斐波那契查找也称黄金分割法,与二分查找和插值查找类似,只是mid的选取有所不同。 Java基础查找算法(2)——二分查找(折半查找) Java基础查找算法(3)——...
  • 斐波那契(黄金分割法)查找算法

    千次阅读 2021-01-15 10:28:48
    文章目录一、斐波那契查找算法概述1.1 什么是斐波那契查找算法1.2 什么是斐波那契数列1.3 斐波那契查找算法的思想二、斐波那契查找的基本步骤三、斐波那契查找的代码实现 一、斐波那契查找算法概述 1.1 什么是...
  • 斐波那契查找算法又称黄金分割查找算法。黄金分割点是把一条线段分成两个部分,使其中一部分与全长之比等于另一部分与这部分之比。取其前三位数字的近似值是0.618。 了解斐波那契查找算法就必须了解斐波那契数列,...
  • 查找算法04-斐波拉契查找4、斐波拉契查找4-1实现代码4-2测试4-3方法解析 4、斐波拉契查找 斐波那契数列介绍:{1, 1, 2, 3, 5, 8, 13, 21, 34, 55 } :斐波那契数列的两个相邻数 的比例,无限接近 黄金分割值0.618。...
  • 1. 线性查找算法 /** * 线性查找算法 * 找到一个满足条件的值就返回,若未查找到,返回-1 * @param arr * @param n * @return */ public static int seqSearch(int []arr,int n){ //线性查找是逐一对比,发现...
  • 平均效率:二分查找>斐波那契查找>顺序查找>插值查找 二分查找和斐波那契查找平均效率大约大10倍。 插值查找虽然是二分查找的升级,但由于超找数组(链表)的值不均匀,导致平均插值查找效率都比顺序查找效率低。 ...
  • 斐波那契查找算法java版

    千次阅读 2014-09-28 19:26:14
    与二分查找相比,斐波那契查找算法的明显优点在于它只涉及加法和减法运算,而不用除法。因为除法比加减法要占去更多的机时,因此,斐波那契查找的平均性能要比折半查找好。 public class Fibonacci_Search ...
  • 斐波那契查找原理与前两种相似,仅仅改变了中间结点(mid)的位置,mid不再是中间或插值得到,而是位于黄金分割点附近。
  • 1、斐波那契查找算法 Fibonacci Search:算法核心思想与二分法相同,只是mid点是黄金分割点; 黄金分割点是把一条线段分割成两个部分,使得一部分与全长之比等于另一部分与这一部分之比,取其前三位的近似值大概是...
  • 各种查找算法性能比较  ①静态查找 折半查找和斐波拉契查找(有序)  ②动态查找 二叉排序树的基本操作 任务: 编写算法实现对依次输入的关键字序列建立二叉排序树 并能实现二叉排序树的查找 插入和删除运算  ...
  • 一、C 程序实现 /****************************************************************************...*Description 斐波那契查找算法 *Author liaoxiongxiong *Version 1.0 *Time 2018-06-28 **************...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,487
精华内容 594
关键字:

斐波拉契查找算法