【算法】二分搜索一个数

news/2024/10/30 9:31:06/

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

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 + 1while (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.ppmy.cn/news/60406.html

相关文章

第十九章 Unity 其他 API

本节介绍一些其他经常使用的Unity类。首先&#xff0c;我们回顾一下Vector3向量类&#xff0c;它既可以表示方向&#xff0c;也可以表示大小。它在游戏中可以用来表示角色的位置&#xff0c;物体的移动/旋转&#xff0c;设置两个游戏对象之间的距离。在我们之前的课程中&#x…

01-微服务部署2023系列-centos安装nginx和jdk教程

centos安装nginx和jdk教程 一、centos安装nginx 0、前提:安装依赖 yum -y install gcc gcc-c++ make libtool zlib zlib-devel openssl openssl-devel pcre pcre-devel 1、压缩包 下载nginx 选择Stable version: http://nginx.org/en/download.html 上传压缩包到…

APSIM模型

随着数字农业和智慧农业的发展&#xff0c;基于过程的农业生产系统模型在模拟作物对气候变化的响应与适应、农田管理优化、作物品种和株型筛选、农田固碳和温室气体排放等领域扮演着越来越重要的作用。APSIM (Agricultural Production Systems sIMulator)模型是世界知名的作物生…

对标世界一流|从Just in time到Just in case ——汽车行业供应链管理经验借鉴

01 丰田汽车精益生产 作为最复杂和最成熟的供应链之一&#xff0c;汽车行业供应链无疑是供应链领域集大成者&#xff0c;而提起汽车行业供应链&#xff0c;就不得不提到丰田汽车&#xff1b;提到丰田汽车&#xff0c;就肯定离不开大名鼎鼎的精益生产以及JIT模式。 JIT模式由丰…

Kafka 权威指南

Kafka 权威指南 这本书于 2021 年看完&#xff0c;2022 年又看了一遍&#xff0c;感觉书读百遍&#xff0c;其义自现。 这本书侧重于 Kafka 的理论知识&#xff0c;虽然书有点老&#xff0c;但是其中关于 Kafka 的基础知识的章节讲得确实不错&#xff0c;适合学习 Kafka 的新手…

【三十天精通Vue 3】第二十六天 Vue3 与 TypeScript 最佳实践

✅创作者:陈书予 🎉个人主页:陈书予的个人主页 🍁陈书予的个人社区,欢迎你的加入: 陈书予的社区 🌟专栏地址: 三十天精通 Vue 3 文章目录 引言一、为什么使用TypeScript?二、Vue 3和TypeScript的基础2.1 安装TypeScript2.2 配置TypeScript2.3 Vue 3中使用TypeScript

Java 版 spring cloud 工程系统管理 工程项目管理系统源码 工程项目各模块及其功能点清单

工程项目各模块及其功能点清单 一、系统管理 1、数据字典&#xff1a;实现对数据字典标签的增删改查操作 2、编码管理&#xff1a;实现对系统编码的增删改查操作 3、用户管理&#xff1a;管理和查看用户角色 4、菜单管理&#xff1a;实现对系统菜单的增删改查操…

Sprinboot+Vue前后端分离的电脑手机服装数码产品商城系统

文章目录 项目介绍主要功能截图:首页商品分类管理数据统计分析家具列表家电详情服装列表部分代码展示设计总结项目获取方式🍅 作者主页:Java韩立 🍅 简介:Java领域优质创作者🏆、 简历模板、学习资料、面试题库【关注我,都给你】 🍅文末获取源码联系🍅 项目介绍 …