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

悠悠 2022-06-04 04:16 359阅读 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 条评论，359人围观）

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

相关阅读

相关 java插值查找算法

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

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

相关查找算法之插值查找

package com.yg.search;/ @author Mu_Mu @date 2020/3/1 10:08 /

梦里梦外;/ 2023年07月10日 08:25/ 0 赞/ 131 阅读

相关查找算法——插值查找（Java实现）

当我们的数组是一个从1到100的有序数组的时候，况且这个时候需要查找的是1，使用二分查找的话，很显然是比较麻烦的。这个时候就要使用到插值查找。插值查找算法类似于二分查找，

冷不防/ 2023年03月13日 13:01/ 0 赞/ 72 阅读

相关数据查找算法：插值查找

1，插值查找基本介绍插值查找的前提条件是目标数组为有序数组插值查找类似于二分查找，不同的是插值查找每次从自适应middle索引开始查找插值查找其实

迷南。/ 2023年02月28日 01:22/ 0 赞/ 115 阅读

相关插值查找算法

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

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

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

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

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

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

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

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

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

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

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

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

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

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

相关插值查找算法实战

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

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