【算法】二分搜索一个数

二分搜索算法是一种高效的搜索算法,用于在已排序的数组中查找特定的元素。其基本思想是将数组分成两个部分,然后确定目标元素可能存在的那一部分,并继续在该部分中进行搜索,直到找到目标元素或确定目标元素不存在为止。具体来说,算法的逻辑如下:

1. 将数组按升序或降序排序。
2. 确定数组的中间元素。
3. 如果中间元素等于目标元素,则返回该元素的索引。
4. 如果中间元素小于目标元素,则在右半部分继续搜索。
5. 如果中间元素大于目标元素,则在左半部分继续搜索。
6. 重复步骤2-5,直到找到目标元素或确定目标元素不存在为止。

需要注意的是,二分搜索算法的时间复杂度为O(log n),其中n是数组中元素的数量。这使得它成为一种非常有效的搜索算法,特别是对于大型数据集。

function binarySearch(arr, target) {
  let left = 0;
  // 此处赋值为最后的索引,再结合while判断条件,搜索区间是个闭合区间,为[left,right]
  let right = arr.length - 1;
  // 此处比较符号是 <= ,这是因为若为 < ,则终止的时候会有一个数,概数没有作比较,会出问题
  // 此时终止条件是 left == right + 1
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

console.log(binarySearch([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 10));//9

二分搜索算法是一种高效的搜索算法,用于在已排序的数组中查找特定的元素。其优点是时间复杂度为O(log n),其中n是数组中元素的数量,这使得它成为一种非常有效的搜索算法,特别是对于大型数据集。相比于线性搜索算法的时间复杂度为O(n),二分搜索算法的时间复杂度更低,因此在处理大型数据集时,它的效率更高。

然而,二分搜索算法也有一些缺点。首先,它要求数组必须是已排序的,如果数组未排序,则需要先对其进行排序,这将增加算法的时间复杂度。其次,二分搜索算法只适用于静态数据集,即数据集不会频繁地插入或删除元素。如果数据集经常发生变化,则需要使用其他算法来维护其有序性。

总之,二分搜索算法是一种高效的搜索算法,特别适用于静态数据集。如果数据集是动态的,则需要考虑其他算法来维护其有序性。

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

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

相关文章

Android APK 反编译后重新打包并签名

APKTool&#xff1a; Apktool 是一个逆向android非常有用的工具&#xff0c;可以用来反编译apk文件&#xff0c;并且能在修改部分资源文件后&#xff0c;重新打包成一个新的apk。 下载连接&#xff1a;http://ibotpeaches.github.io/Apktool/install/ 下载之后文件夹非常清爽&…

ChatGPT会颠覆SEO内容创作吗

近几年 AI 的发展日新月异。除了搜索算法本身大规模应用人工智能&#xff0c;我也一直关注着 AI 用于写作的进展。 上篇关于 Google 有用内容更新的帖子还在说&#xff0c;高质量内容创作是 SEO 最难的事之一&#xff0c;对某些网站来说&#xff0c;如果能有工具帮助&#xff…

Mysql 日志

目录 0 课程视频 1 错误日志 -> 默认开启 1.1 查看变量 show variables like %log_error%; 1.2 文件位置 /var/log -> mysqld.log 1.3 指令语法 2 二进制日志 -> 修改数据和数据库结构的日志 2.1 记录原则 2.1.1 记录 数据库创建语句 和 增删改查 2.1.2 不记…

JdbcTemplate常用语句代码示例

目录 JdbcTemplate 需求 官方文档 JdbcTemplate-基本介绍 JdbcTemplate 使用实例 需求说明 创建数据库 spring 和表 monster 创建配置文件 src/jdbc.properties 创建配置文件 src/JdbcTemplate_ioc.xml 创建类JdbcTemplateTest测试是否可以正确得到数据源 配置 J…

智能算法系列之基于粒子群优化的模拟退火算法

文章目录 前言1. 算法结合思路2. 问题场景2.1 Sphere2.2 Himmelblau2.3 Ackley2.4 函数可视化 3. 算法实现代码仓库&#xff1a;IALib[GitHub] 前言 本篇是智能算法(Python复现)专栏的第四篇文章&#xff0c;主要介绍粒子群优化算法与模拟退火算法的结合&#xff0c;以弥补各自…

《基于EPNCC的脉搏信号特征识别与分类研究》阅读笔记

目录 一、论文摘要 二、论文十问 三、论文亮点与不足之处 四、与其他研究的比较 五、实际应用与影响 六、个人思考与启示 参考文献 一、论文摘要 为了快速获取脉搏信号的完整表征信息并验证脉搏信号在相关疾病临床诊断中的敏感性和有效性。在本文中&#xff0c;提出了一…

Ubantu docker学习笔记(八)私有仓库

文章目录 一、建立HTTPS链接1.在仓库服务器上获取TLS证书1.1 生成证书颁发机构证书1.2 生成服务器证书1.3 利用证书运行仓库容器 2.让私有仓库支持HTTPS3.客户端端配置 二、基本身份验证三、对外隐藏仓库服务器3.1 在服务器端3.2 在客户端进行 四、仓库可视化 在前面的学习中&a…

ChatGPT被淘汰了?Auto-GPT到底有多强

大家好&#xff0c;我是可夫小子&#xff0c;关注AIGC、读书和自媒体。解锁更多ChatGPT、AI绘画玩法。 说Auto-GPT淘汰了ChatGPT了&#xff0c;显然是营销文案里面的标题党。毕竟它还是基于ChatGPT的API&#xff0c;某种意义只是基于ChatGPT能力的应用。但最近&#xff0c;Auto…

Nautilus Chain Layer 3 圆桌会议圆满举办,超4.8K用户观看

在4月21日&#xff0c;Nautilus Chain举办了以“Layer 3区块链的意义和发展以及Crypto的演变”为主题的线上圆桌会议&#xff0c;我们邀请了众多行业嘉宾包括GitcoinDAO社区管理者Bob jiang、Whalers Community发起者崔棉大师、Chatpuppy联合创始人 古千峰、Whalers Community核…

机器学习与深度学习——通过决策树算法分类鸢尾花数据集iris求出错误率画出决策树并进行可视化

什么是决策树&#xff1f; 决策树是一种常用的机器学习算法&#xff0c;它可以对数据集进行分类或回归分析。决策树的结构类似于一棵树&#xff0c;由节点和边组成。每个节点代表一个特征或属性&#xff0c;每个边代表一个判断或决策。从根节点开始&#xff0c;根据特征的不同…

vue3的props和defineProps

文章目录 1. Props 声明1.1 props用字符串数组来声明Blog.vueBlogPost.vue 1.2 props使用对象来声明Blog.vueBlogPost.vue 2. 传递 prop 的细节2.1 Prop 名字格式2.1 静态Prop & 动态 Prop静态prop动态prop示例Blog.vueBlogPost.vue 2.3 传递不同的值类型NumberBooleanArra…

基于YOLOv4的目标检测系统(附MATLAB代码+GUI实现)

摘要&#xff1a;本文介绍了一种MATLAB实现的目标检测系统代码&#xff0c;采用 YOLOv4 检测网络作为核心模型&#xff0c;用于训练和检测各种任务下的目标&#xff0c;并在GUI界面中对各种目标检测结果可视化。文章详细介绍了YOLOv4的实现过程&#xff0c;包括算法原理、MATLA…

C++知识点 -- 异常

C知识点 – 异常 文章目录 C知识点 -- 异常一、异常概念二、异常的使用1.异常的抛出和捕获2.异常的重新抛出3.异常安全4.异常规范 三、自定义异常体系四、C标准库的异常体系五、C异常的优缺点 一、异常概念 当一个函数发现自己无法处理错误时&#xff0c;就可以抛出异常&#…

14-3-进程间通信-消息队列

前面提到的管道pipe和fifo是半双工的&#xff0c;在某些场景不能发挥作用&#xff1b; 接下来描述的是消息队列&#xff08;一种全双工的通信方式&#xff09;&#xff1b; 比如消息队列可以实现两个进程互发消息&#xff08;不像管道&#xff0c;只能1个进程发消息&#xff…

kali: kali工具-Ettercap

kali工具-Ettercap ettercap工具&#xff1a; 用来进行arp欺骗&#xff0c;可以进行ARP poisoning&#xff08;arp投毒&#xff09;&#xff0c;除此之外还可以其他功能&#xff1a; ettercap工具的arp投毒可以截取web服务器、FTP服务器账号密码等信息&#xff0c;简略后打印出…

前端学习之使用JavaScript

前情回顾&#xff1a;网页布局 JavaScript 简介 avaScript诞生于1995年&#xff0c;它的出现主要是用于处理网页中的前端验证。所谓的前端验证&#xff0c;就是指检查用户输入的内容是否符合一定的规则。比如&#xff1a;用户名的长度&#xff0c;密码的长度&#xff0c;邮箱的…

SQL中去除重复数据的几种方法,我一次性都告你​

使用SQL对数据进行提取和分析时&#xff0c;我们经常会遇到数据重复的场景&#xff0c;需要我们对数据进行去重后分析。 以某电商公司的销售报表为例&#xff0c;常见的去重方法我们用到distinct 或者group by 语句&#xff0c; 今天介绍一种新的方法&#xff0c;利用窗口函数…

Github 的使用

3. Github 在版本控制系统中&#xff0c;大约90%的操作都是在本地仓库中进行的&#xff1a;暂存&#xff0c;提交&#xff0c;查看状态或者历史记录等等。除此之外&#xff0c;如果仅仅只有你一个人在这个项目里工作&#xff0c;你永远没有机会需要设置一个远程仓库。只有当你…

2001-2021年全国30省就业人数数据

2001-2021年全国30省就业人数数据/各省就业人数数据 1、时间&#xff1a;2001-2021年 2、范围&#xff1a;包括30个省市不含西藏 3、指标&#xff1a;就业人数 4、来源&#xff1a;各省NJ、社会统计NJ 5、缺失情况说明&#xff1a;无缺失 6、指标说明&#xff1a; 就业人…

实在智能出席第六届数字中国建设峰会,入围2022年信息技术应用创新优秀解决方案榜单

最美榕城四月天&#xff0c;山海之间尽显数字澎湃。这一周来&#xff0c;实在智能来到了“有福之州”&#xff0c;为数字中国建设增添实在色彩。 4月25日&#xff0c;实在华夏行抵达福州站&#xff0c;与众多生态合作伙伴携手共话数字发展新未来&#xff1b; 4月26日&#xff…
最新文章