Javascript 插值搜索与二分搜索

        插值搜索和二分搜索都是在有序数组中查找目标元素的算法。它们之间的核心区别在于确定中间元素的方式。
        1、二分搜索(Binary Search):二分搜索是一种通过将目标值与数组中间元素进行比较,然后根据比较结果缩小搜索范围的算法。如果中间元素等于目标值,则找到目标;如果中间元素大于目标值,则在左半部分继续搜索;如果中间元素小于目标值,则在右半部分继续搜索。这样不断缩小搜索范围,直到找到目标或确定目标不存在。
        2、插值搜索(Interpolation Search):插值搜索是一种根据目标值在已知范围内的分布情况,预测目标值应该在的位置,然后进行搜索的算法。通过计算估计的位置(插值位置),然后进行比较,再根据比较结果缩小搜索范围。插值搜索通常在数据元素分布比较均匀的情况下效果更好,能比二分搜索更快地收敛到目标值。

        经过定义理解,二分搜索是通过比较中间元素来划分搜索范围,每次将搜索范围缩小一半;插值搜索是通过估计目标值在数组中的位置,根据估计位置缩小搜索范围。插值搜索在数据分布比较均匀且连续的情况下可能更快,但在非均匀或者不连续的情况下可能不如二分搜索。

对于有序且均匀分布的数组,插值搜索比二分搜索效果更好。 

        无论搜索键如何,二分搜索都会转到中间元素进行检查。另一方面,插值搜索可以根据搜索关键字去不同的位置。如果搜索键的值接近最后一个元素,则插值搜索可能会向末尾开始搜索。

        插值搜索和二分搜索都是用于在排序列表或数组中搜索特定元素的算法。两种算法的平均时间复杂度均为 O(log n),这意味着执行搜索所需的时间随着列表的大小呈对数增长。

但是,插值搜索和二分搜索之间存在一些关键区别:

        插值搜索根据目标元素周围元素的值来估计目标元素的位置,而二分搜索总是从检查列表的中间元素开始。

        当列表中的元素均匀分布时,插值搜索比二分搜索更有效,而当列表中的元素不均匀分布时,二分搜索更有效。

        插值搜索可能比二分搜索需要更长的时间来实现,因为它需要使用额外的计算来估计目标元素的位置。

例子 : 

function interpolation_search(arr, target){
    let low = 0;
    let high = arr.length - 1;
 
    while (low <= high && target >= arr[low] && target <= arr[high]){
         
        // Calculate the position of the target element based on its value
        let pos = low + Math.floor(((target - arr[low]) * (high - low)) / (arr[high] - arr[low]));
         
        // Check if the target element is at the calculated position
        if(arr[pos] == target){
            return pos;
        }
 
        // If the target element is less than the element at the calculated position, search the left half of the list
        if(arr[pos] > target){
            high = pos - 1;
        }
        else{
            // If the target element is greater than the element at the calculated position, search the right half of the list
            low = pos + 1;
        }
    }
    return -1;
}
 
let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
let target = 5;
 
let index = interpolation_search(arr, target);
 
if (index == -1){
    console.log(target, " not found in the list");
}
else{
    console.log(target, " found at index ", index);
}
 
// The code is written by Nidhi goel. 

输出
在索引 4 处找到 5 个

        插值搜索平均进行 log(log(n)) 次比较(如果元素均匀分布),其中 n 是要搜索的元素数量。在最坏的情况下(例如键的数值呈指数增加),它可以进行 O(n) 比较。 

时间复杂度: O(log(log n)) 

空间复杂度: O(1)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/576026.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

ubuntu16安装docker及docker-compose

ubuntu16安装docker及docker-compose 一、环境前期准备 检查系统版本 系统版本最好在16及以上&#xff0c;可以确保系统的兼容性 lsb_release -a查看内核版本及系统架构 建议用 x86_64的系统架构&#xff0c;安装是比较顺利的 uname -a32的系统不支持docker&#xff0c;安…

Adipogen--Progranulin (rat) ELISA Kit

Progranulin (PGRN)是一种广泛表达的多能生长因子&#xff0c;通过激活控制细胞周期进展和细胞运动的信号级联反应&#xff0c;在发育、创伤修复和炎症等过程中发挥作用。它在中枢神经系统中的功能值得关注&#xff0c;因为在额颞退行性变(FTLD)病例中发现了PGRN基因突变。此外…

2024年618有哪些数码家电值得入手?全网最省钱攻略指南

作为全年唯一设在夏季的大型电商狂欢节&#xff0c;618一直是很多人购置数码类、家电类的最好时间节点之一。但是问题来了&#xff0c;现在的数码家电行业“鱼龙混杂”&#xff0c;不仅越来越多新品牌涌入市场&#xff0c;而且各个大品牌为了抢占市场&#xff0c;旗下产品的品类…

ArcGIS专题图制作—3D海底地形

这一期的制图教程将带我们走入马里亚纳海沟&#xff0c;让我们一起绘制这张美妙的地图吧&#xff01;视频也上传到了B站&#xff0c;小伙伴可以去支持一下。 【制图教程】ArcGIS Pro绘制3D海底地形图 B站视频链接&#xff1a;【制图教程】ArcGIS Pro绘制3D海底地形图_哔哩哔哩…

7-31 字符串循环左移

题目链接&#xff1a;7-31 字符串循环左移 一. 题目 1. 题目 2. 输入输出样例 3. 限制 二、代码(python) 1. 代码实现 str1 input().split(\n)[0] num int(input()) len len(str1) if num > len:num num % len # 减少移动次数 print(str1[num:] str1[:num])2. 提交…

Spring Boot携手OAuth2.0,轻松实现微信扫码登录!

作者介绍&#xff1a;✌️大厂全栈码农|毕设实战开发&#xff0c;专注于大学生项目实战开发、讲解和毕业答疑辅导。 推荐订阅精彩专栏 &#x1f447;&#x1f3fb; 避免错过下次更新 Springboot项目精选实战案例 更多项目&#xff1a;CSDN主页YAML墨韵 学如逆水行舟&#xff0c…

21.基础乐理-等音调扩展篇、为何一共十五个大调

首先 等音调 的概念是基于 等音 的概念&#xff0c;比如下图中的音名&#xff1a;因为用的按键相同&#xff0c;音名不同&#xff0c;所以被称为等音调 然后音名一共有35个&#xff0c;如下图&#xff1a;所以在理论上它会有35个大调&#xff0c;但是人总是倾向于选择简单、简洁…

关于pdf.js中文本坐标尺寸的使用

一个电子教材项目中有这样一个需求&#xff1a; 用户向网站上传一个PDF书籍后&#xff0c;网站可以对PDF书籍进行解析&#xff0c;并支持用户对PDF书籍的每一页做一些操作&#xff0c;比如&#xff1a;为英语课本的单词和句子添加音频热区。因为热区数量很多&#xff0c;所以&a…

C# 图像处理 添加水印

方法1&#xff0c;使用自带的画刷进行绘制水印 示例代码 public partial class Form1 : Form{public Form1(){InitializeComponent();}string photoPathstring.Empty;Bitmap image null;private void button1_Click(object sender, EventArgs e) //选择照片{OpenFileDialog d…

LDA主题模型

在文本挖掘领域&#xff0c;大量的数据都是非结构化的&#xff0c;很难从信息中直接获取相关和期望的信息&#xff0c;一种文本挖掘的方法&#xff1a;主题模型&#xff08;Topic Model&#xff09;能够识别在文档里的主题&#xff0c;并且挖掘语料里隐藏信息&#xff0c;并且在…

Windows 下载、安装和使用 Postman 的详细教程!

Postman 是一个功能强大的API测试工具&#xff0c;它可以帮助程序员更轻松地测试和调试 API。在本文中&#xff0c;我们将讨论如何在 Windows 上安装和使用 Postman。 安装 Postman 首先&#xff0c;让我们从 Postman 的官方网站下载并安装&#xff1a;https://www.postman.c…

YOLOV5 TensorRT部署 BatchedNMS(engine模型推理)(下)

主要是在王新宇代码的基础上改进,引入对BatchedNMS的解码 文章目录 1. 修改yolov5.cpp2.修改yololayer.h1. 修改yolov5.cpp 首先增加全局变量,名字根据转onnx时修改的节点名字来,查看onnx文件可以看到,顺序不要弄错。 const char *INPUT_NAME = “images”; const char …

C语言——贪吃蛇游戏的实现

目录 一. 贪吃蛇的介绍 二. Win32 API 1. 控制台程序 2. COORD 控制台屏幕上的坐标 3. GetStdHandle 4. GetConsoleCursorInfo CONSOLE_CURSOR_INFO 5. SetConsoleCursorInfo 6. SetConsoleCursorPosition 封装的SetPos函数 7. GetAsyncKeyState 宏定义KEY_PRESS 三…

Jackson 2.x 系列【31】Spring Boot 集成之字典回写

有道无术&#xff0c;术尚可求&#xff0c;有术无道&#xff0c;止于术。 本系列Jackson 版本 2.17.0 本系列Spring Boot 版本 3.2.4 源码地址&#xff1a;https://gitee.com/pearl-organization/study-jaskson-demo 文章目录 1. 场景描述2. 案例演示2.1 修改枚举2.2 定义注解…

【Go语言】接口类型(一)接口类型与接口的值

本文是介绍golang接口类型的第一篇&#xff0c;主要介绍接口类型与接口类型的值的相关概念。 1. 静态类型、动态类型、动态值 所谓的静态类型&#xff08;即 static type&#xff09;&#xff0c;就是变量声明的时候的类型。 var age int // int 是静态类型 var name strin…

MQ面试题

为什么要使用消息队列&#xff1f; 优点&#xff1a;解耦、异步、流量削峰 缺点&#xff1a;可用性降低、复杂性提高、一致性问题 为什么选择了RabbitMQ而不是其它的MQ&#xff1f; kafka是以吞吐量高而闻名&#xff0c;不过其数据稳定性一般&#xff0c;而且无法保证消息有…

关于Android中的限定符

很多对于Android不了解或是刚接触Android的初学者来说&#xff0c;对于Android开发中出现的例如layout-large或者drawable-xxhdpi这样的文件夹赶到困惑&#xff0c;这这文件夹到底有什么用&#xff1f;什么时候用&#xff1f;这里简单的说一下。 其实&#xff0c;在上面例子中&…

day05 51单片机-外部中断、定时器

1 外部中断——按键控制LED亮灭 1.1 需求描述 本案例通过检测SW3触发的外部中断实现P00对应LED的亮灭。 1.2 硬件设计 1.2.1 中断简介 单片机中断是一种重要的计算机编程概念,用于处理在程序执行过程中突然发生的事件或条件。这些事件可以是外部硬件触发的,如按下按钮、…

SpringBoot+vue开发记录(二)

说明&#xff1a;本篇文章的主要内容为SpringBoot开发中后端的创建 项目创建: 1. 新建项目&#xff1a; 如下&#xff0c;这样简单创建就行了&#xff0c;JDK什么的就先17&#xff0c;当然1.8也是可以的&#xff0c;后面可以改。 这样就创建好了&#xff1a; 2. pom.xml…

【面试经典 150 | 回溯】电话号码的字母组合

文章目录 写在前面Tag题目来源解题思路方法一&#xff1a;回溯 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法&#xff0c;两到三天更新一篇文章&#xff0c;欢迎催更…… 专栏内容以分析题目为主&#xff0c;并附带一些对于本题涉及到的数据结构等内容进行回顾…