学习回顾算法（插值查找算法）

悠悠 2022-06-04 04:16 247阅读 0赞

## 插值查找算法概述 ##

插值查找算法，是二分法查找算法的改进。将查找点的选择改为自适应选择，可以提高查找效率。  
算法注意点和二分法查找一样，都需要列表先排好序。

## 插值查找算法实现 ##

**1、golang实现**

package main
    
    import (
        "fmt"
    )
    func InsertionSearch(values []int, key int) int {
        if len(values) == 0 || key > values[len(values)-1] || key < values[0] {
            return -1
        }
        front := 0
        end := len(values) - 1
        mid := front + ((key-values[front])/(values[end]-values[front]))*(end-front)
        for front < end && values[mid] != key {
            if values[mid] > key {
                end = mid - 1
            } else {
                front = mid + 1
            }
            mid = front + ((key-values[front])/(values[end]-values[front]))*(end-front)
            if mid > end {
                mid = end
            }
        }
    
        if values[mid] == key {
            return mid
        }
    
        return -1
    }
    
    func main() {
    
        values := []int{
       1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39}
        fmt.Println(values)
        index := InsertionSearch(values, 1)
        fmt.Println(index)
        index = InsertionSearch(values, 35)
        fmt.Println(index)
        return
    }

结果

[1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 33 35 37 39]
    0
    17

发表评论取消回复

表情：

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

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

相关阅读

相关【算法系列 | 11】深入解析查找算法之—插值查找

查找算法是计算机科学中的一类算法，用于在数据集中寻找特定值或数据项。其目标是确定数据是否存在于给定的数据结构中，并找到数据项的位置（索引）或其他相关信息。不同的查找算法适...

喜欢ヅ旅行/ 2024年04月28日 08:09/ 0 赞/ 53 阅读

相关 java插值查找算法

1. 插值查找原理介绍: 插值查找算法类似于二分查找，不同的是插值查找每次从自适应 mid 处开始查找。 1. 将折半查找中的求 mid 索引的公式 , low 表示左

ゞ浴缸里的玫瑰/ 2024年03月27日 13:24/ 0 赞/ 80 阅读

相关插值查找算法

插值查找算法是基于二分查找算法的,只是在查找的过程中计算Middle的方式有所改变,比如一组可以通过二分查找算法计算出的nMid索引的值,是这样子计算的 nMid=(nLow

淡淡的烟草味﹌/ 2022年08月07日 11:58/ 0 赞/ 162 阅读

相关学习回顾算法（插值查找算法）

插值查找算法概述插值查找算法，是二分法查找算法的改进。将查找点的选择改为自适应选择，可以提高查找效率。算法注意点和二分法查找一样，都需要列表先排好序。插值查

悠悠/ 2022年06月04日 04:16/ 0 赞/ 248 阅读

相关学习回顾算法（二分法查找）

二分法查找概述二分法查找也称为折半查找，属于有序查找算法。用给定值key先和中间结点的关键字比较，中间结点把线形表分成两个字表，若相等则查找成功；若不相等，再根据key

ゞ浴缸里的玫瑰/ 2022年06月04日 04:12/ 0 赞/ 199 阅读

相关学习回顾算法（顺序查找算法）

顺序查找算法概述顺序查找算法是在一个已知无序（或有序）队列中找出关键字相同的数的具体位置。顺序查找算法原理让关键字和队列中的数从最后一个开始逐个比较，直到找出与给

深藏阁楼爱情的钟/ 2022年06月04日 04:08/ 0 赞/ 171 阅读

相关查找算法：插值查找算法实现及分析

插值查找算法介绍插值查找（Interpolation Search）是根据要查找关键字key与查找表中最大最小记录的关键字比较后的查找方法，其核心就在于插值的计算公式k

川长思鸟来/ 2022年05月29日 22:52/ 0 赞/ 246 阅读

相关 java实现插值查找算法

一、介绍 1、插值查找算法类似于二分查找，不同的是插值查找每次从自适应 mid 处开始查找。 2、将折半查找中的求mid索引的公式,low表示左边索引left,hig

逃离我推掉我的手/ 2021年11月11日 04:38/ 0 赞/ 318 阅读

相关 java实现插值查找算法

一、介绍 1、插值查找算法类似于二分查找，不同的是插值查找每次从自适应 mid 处开始查找。 2、将折半查找中的求mid索引的公式,low表示左边索引left,hig

素颜马尾好姑娘i/ 2021年10月15日 04:33/ 0 赞/ 322 阅读

相关插值查找算法实战

一插值查找原理插值查找算法类似于二分查找，不同的是插值查找每次从自适应 mid 处开始查找。二插值查找公式将二分查找中的求 mid 索引的公式进行改造

港控/mmm°/ 2021年07月24日 16:51/ 0 赞/ 421 阅读