二分查找、插值查找、斐波那契查找

朴灿烈づ我的快乐病毒、 2022-05-16 04:28 220阅读 0赞

# 1 二分查找 #

在有序表中，取**中间记录**作为比较对象，将其与给定值相比较，若其等于给定值，则查找成功；若其小于给定值，则在中间记录的右半区继续查找；若其大于给定值，则在中间记录的左半区继续查找。不断重复以上过程，直到查找成功或无匹配记录。

**使用该查找方法的前提条件在于，线性表中的数据必须有序，且必须采用顺序存储的方式。**

var array = [1,2,3,4,5,6,7,8,9]
    
    function search(value){
        let low = 0, high = array.length - 1;
        let mid;
    
        while (low <= high){
            mid = parseInt((low + high)/2);
            if (array[mid] > value){
                high = mid - 1;
            }else if (array[mid] < value){
                low = mid + 1;
            }else{
                break;
            }
        }
    
        if (array[mid] === value) return mid;
        return -1;
    }
    
    console.log('查找3',search(3));
    console.log('查找8',search(8));
    console.log('查找10',search(10));

![这里写图片描述][70]

# 2 插值查找 #

插值查找与二分查找的原理类似，区别就在于mid值的选取。  
在插值查找中，`mid = low + ( (key - a[low]) / (a[high] - a[low]) ) * (high - low)`。该算法对表长较大，而关键字分布比较均匀的情况下，性能较高，而对于分布不均匀的数据，则不太适用。

var array = [1,2,3,4,5,6,7,8,9]
    
    function search(value){
        let low = 0, high = array.length - 1;
        let mid;
    
        while (low <= high){
            mid = parseInt( low + (value-array[low]) / (array[high]-array[low]) * (high - low) );
            if (array[mid] > value){
                high = mid - 1;
            }else if (array[mid] < value){
                low = mid + 1;
            }else{
                break;
            }
        }
        if (array[mid] === value) return mid;
        return -1;
    }

# 3斐波那契查找 #

顾名思义，该查找方法利用了斐波那契数列，该方法的主要思路为，先在斐波那契数列F中找到第`k`项，使其满足，`F[k]-1 > 有序数组的最大索引号 > F[k-1]-1`，然后将数组扩充到长度为`F[K]-1`，并使扩充项的值都等于有序数组的最后一项。  
分割点的索引为`mid = low + F[K-1]-1`，此时有序数组被mid划分为两段，左段长度为`F[K-1]-1`，右段长度为`F[k-2]-1`。若查找值大于mid值，则low等于mid+1，而k = k - 2；若查找值小于mid，则high = mid -1，k =k -1.

![这里写图片描述][70 1]

var array = [1,2,3,4,5,6,7,8,9]
    var F = [0,1,1,2,3,5,8,13,21,34]
    
    function search(value){ 
        let low = 0, high = array.length - 1，n= array.length - 1;
        let mid,k=0;
    
        while (high > F[k]-1){  //寻找第k项
            k++;
        }
    
        for (let i=high; i<F[k]-1; i++){   //补全有序数组
            array[i] = array[high];
        }
    
        while (low <= high){
            mid = low + F[k-1] -1;
            if (array[mid] > value){
                high = mid - 1;
                k -= 1;         //长度缩减为 F[k-1] -1
            }else if (array[mid] < value){
                low = mid + 1;
                k -= 2;         //长度缩减为 F[k-2] -1
            }else{
                if (mid <= n)  //相等则找到位置
                    return mid;
                else           //大于原始长度，则说明等于数组最后一项
                    return n;
            }
        }
    
        return -1;
    }

[70]: /images/20220516/21bed20537c94b9c837a111d72e4867f.png
[70 1]: /images/20220516/1ca65a4b5fd84d2fa6eb2f0e877b525e.png

发表评论取消回复

表情：

评论列表（有 0 条评论，220人围观）

还没有评论，来说两句吧...

相关阅读

相关【算法】顺序查找、二分查找、插值查找、斐波那契查找 (源码和思路)

目录查找算法 1.线性(顺序)查找 (1)思路 (2)代码实现(java) 2.二分(折半)查

Bertha 。/ 2023年09月23日 19:21/ 0 赞/ 130 阅读

相关 Java数据结构与算法_06 查找算法（顺序查找、二分查找、插值查找、斐波那契查找）

Java数据结构与算法\_06 顺序(线性)查找完整代码二分查找/折半查找完整代码插值查找完整代码

淡淡的烟草味﹌/ 2023年07月12日 11:43/ 0 赞/ 1 阅读

相关查找之斐波那契查找详解

折半查找是从中间分，也就是说每一次查找总是一分为二，无论数据大小，很多时候这并不是最合理的做法。斐波那契查找（Fibonacci Search）,利用黄金分割的思想

- 日理万妓/ 2022年12月14日 13:36/ 0 赞/ 213 阅读

相关什么是二分查找、插值查找、斐波那契查找和索引查找？

引言原文链接：[顺序表和有序表的查找算法][Link 1] [线性索引查找][Link 2] 希望点进去的小伙伴关注一下我的公众号哟，文末有二维码，谢谢！ 1

Love The Way You Lie/ 2022年11月19日 14:59/ 0 赞/ 198 阅读

相关 Java有序表查找：折半查找、二分查找、差值查找和斐波那契查找

Java有序表查找：折半查找、二分查找、差值查找和斐波那契查找【[尊重][Link 1] [原创，转载请注明出处][Link 1] 】http://bl

分手后的思念是犯贱/ 2022年07月26日 08:50/ 0 赞/ 183 阅读

相关二分查找、插值查找、斐波那契查找

1 二分查找在有序表中，取中间记录作为比较对象，将其与给定值相比较，若其等于给定值，则查找成功；若其小于给定值，则在中间记录的右半区继续查找；若其大于给定值，则在中间记

朴灿烈づ我的快乐病毒、/ 2022年05月16日 04:28/ 0 赞/ 221 阅读

相关斐波那契查找

斐波那契查找实验数据表明当数据量超过40万时，斐波那契查找算法查找速度优于二分查找原理：与二分查找相比，斐波那契查找的明显优点在于它只涉及加法和减法运算，而不用除法

约定不等于承诺〃/ 2022年04月25日 01:26/ 0 赞/ 292 阅读

相关斐波那契查找

1. 问题描述我们知道，对于有序数据序列进行查找，二分查找法性能是相当好的，时间效率达到O(log2n)，但该算法其实还有些可以进行改进的地方。普通的折半查找直接通过折

Bertha 。/ 2022年03月28日 10:46/ 0 赞/ 283 阅读

相关斐波那契查找

Introduce 黄金分割查找，区别于插值查找找0.5，斐波那契查找找0.618。 ![18721752-80ed4220f6009617.png][]

野性酷女/ 2021年09月30日 08:46/ 0 赞/ 387 阅读

相关【数据结构与算法 12】二分查找、插值查找、斐波那契查找

一、前言查找是在大量的信息中寻找一个特定的信息元素，在计算机应用中，查找是常用的基本运算，例如在编译程序中符号表的查找。本文简单介绍二分查找、插值查找、斐波那契查找

超、凢脫俗/ 2021年08月30日 00:38/ 0 赞/ 351 阅读