当前位置: 首页 > news >正文

二分搜索简介

概念

二分搜索算法(Binary Search)是一种高效的搜索算法,用于在有序数组中查找特定元素的位置。它的基本思想是将数组分为两部分,通过比较目标值与数组中间元素的大小关系,确定目标值可能存在的区间,然后不断缩小区间直到找到目标值或确定不存在。二分搜索算法是一种分治法的应用,通过将问题分解为更小的子问题,逐步缩小搜索范围。

二分搜索算法用于在有序数组中查找特定元素的位置,即确定目标值在数组中的索引。

算法特点

  1. 二分搜索算法要求有序数组,因为它是通过比较目标值与中间元素的大小关系来确定搜索范围的。
  2. 算法通过将搜索范围不断缩小一半,具有较高的效率。
  3. 二分搜索算法的时间复杂度为O(log n),其中n为数组的长度。

优点

  • 高效:二分搜索算法的时间复杂度较低,适用于大规模数据集。
  • 简单:算法思想简单直观,易于理解和实现。
  • 适用范围广:适用于有序数组的查找问题。

缺点

  • 依赖有序数组:二分搜索算法要求输入数组是有序的,如果数组无序,则需要先进行排序。
  • 不适用于动态数据集:如果数据集需要频繁插入或删除元素,二分搜索算法的效率会较低。

适用场景

  • 二分搜索算法适用于已经排序的静态数据集,例如查找某个元素在字典中的位置、查找某个数字是否在排序好的数组中等。

实现代码

public class BinarySearch {public static int binarySearch(int[] arr, int target) {int left = 0;int right = arr.length - 1;while (left <= right) {int mid = left + (right - left) / 2;if (arr[mid] == target) {return mid;} else if (arr[mid] < target) {left = mid + 1;} else {right = mid - 1;}}return -1;}public static void main(String[] args) {int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};int target = 6;int result = binarySearch(arr, target);if (result == -1) {System.out.println("目标元素不存在");} else {System.out.println("目标元素的索引为 " + result);}}
}

相关文章:

二分搜索简介

概念&#xff1a; 二分搜索算法&#xff08;Binary Search&#xff09;是一种高效的搜索算法&#xff0c;用于在有序数组中查找特定元素的位置。它的基本思想是将数组分为两部分&#xff0c;通过比较目标值与数组中间元素的大小关系&#xff0c;确定目标值可能存在的区间&…...

虚拟车衣VR云展厅平台扩大了展览的触达范围

传统展厅主要是以静态陈列的形式来传达内容&#xff0c;主要的展示形式有图片、视频等&#xff0c;具有一定的局限性&#xff0c;体验感较差&#xff0c;客户往往不能深入地了解信息和细节内容。 VR全景看车是通过虚拟现实技术实现逼真的汽车观赏和试乘体验。消费者可以通过智能…...

云部署家里的服务器

1.固定静态ip 查看ip地址&#xff0c;en开头的 ifconfig查看路由器ip&#xff0c;via开头的 ip route修改配置文件 cd /etc/netplan/ #来到这个文件夹 sudo cp 01-network-manager-all.yaml 01-network-manager-all.yaml.bak #先备…...

【利用冒泡排序的思想模拟实现qsort函数】

1.qsort函数 1.1qsort函数的介绍 资源来源于cplusplus网站 1.2qsort函数的主要功能 对数组的元素进行排序 对数组中由 指向的元素进行排序&#xff0c;每个元素字节长&#xff0c;使用该函数确定顺序。 此函数使用的排序算法通过调用指定的函数来比较元素对&#xff0c;并将指…...

[plugin:vite:css] [sass] Undefined mixin.

前言&#xff1a; vite vue3 TypeScript环境 scss报错&#xff1a; [plugin:vite:css] [sass] Undefined mixin. 解决方案&#xff1a; 在vite.config.ts文件添加配置 css: {preprocessorOptions: {// 导入scss预编译程序scss: {additionalData: use "/resources/_ha…...

【论文阅读】大语言模型中的文化道德规范知识

摘要&#xff1a; 在已有的研究中&#xff0c;我们知道英语语言模型中包含了类人的道德偏见&#xff0c;但从未有研究去检测语言模型对不同国家文化的道德差异。 我们分析了语言模型包含不同国家文化道德规范的程度&#xff0c;主要针对两个方面&#xff0c;其一是看语言模型…...

51单片机实训项目之产品数量计数器

/********************************************************************************* * 【实验平台】&#xff1a; QX-MCS51 单片机开发板 * 【外部晶振】&#xff1a; 11.0592mhz * 【主控芯片】&#xff1a; STC89C52 * 【编译环境】&#xff1a; Keil μVisio3 * 【程序…...

Scala第七章节

Scala第七章节 scala总目录 章节目标 掌握继承和抽象类相关知识点掌握匿名内部类的用法了解类型转换的内容掌握动物类案例 1. 继承 1.1 概述 实际开发中, 我们发现好多类中的内容是相似的(例如: 相似的属性和行为), 每次写很麻烦. 于是我们可以把这些相似的内容提取出来单…...

C语言进程的相关操作

C语言进程的相关操作 进程简介 每个进程都有一个非负整数形式到的唯一编号&#xff0c;即PID&#xff08;Process Identification&#xff0c;进程标识&#xff09;PID在任何时刻都是唯一的&#xff0c;但是可以重用&#xff0c;当进程终止并被回收以后&#xff0c;其PID就可…...

数据结构学习系列之链式栈

链式栈&#xff1a;即&#xff1a;栈的链式存储结构&#xff1b;分析&#xff1a;为了提高程序的运算效率&#xff0c;应采用头插法和头删法&#xff1b;进栈&#xff1a; int push_link_stack(stack_t *link_stack,int data) {if(NULL link_stack){printf("入参合理性检…...

too many session files in /var/tmp

Linux中Too many open files 问题分析和解决_e929: too many viminfo temp files-CSDN博客...

【7.0】打开未知来源安装应用

默认打开未知来源安装应用 frameworks\base\packages\SettingsProvider\res\values\defaults.xml <bool name"def_install_non_market_apps">false</bool>...

安装ipfs-swarm-key-gen

安装ipfs-swarm-key-gen Linux安装go解释器安装ipfs-swarm-key-gen Linux安装go解释器 https://blog.csdn.net/omaidb/article/details/133180749 安装ipfs-swarm-key-gen # 编译ipfs-swarm-key-gen二进制文件 go get -u github.com/Kubuxu/go-ipfs-swarm-key-gen/ipfs-swarm…...

BASH shell脚本篇5——文件处理

这篇文章介绍下BASH shell中的文件处理。之前有介绍过shell的其它命令&#xff0c;请参考&#xff1a; BASH shell脚本篇1——基本命令 BASH shell脚本篇2——条件命令 BASH shell脚本篇3——字符串处理 BASH shell脚本篇4——函数 在Bash Shell脚本中&#xff0c;可以使用…...

ElementUI之首页导航及左侧菜单(模拟实现)

目录 ​编辑 前言 一、mockjs简介 1. 什么是mockjs 2. mockjs的用途 3. 运用mockjs的优势 二、安装与配置mockjs 1. 安装mockjs 2. 引入mockjs 2.1 dev.env.js 2.2 prod.env.js 2.3 main.js 三、mockjs的使用 1. 将资源中的mock文件夹复制到src目录下 2. 点击登…...

Java开源工具库使用之Lombok

文章目录 前言一、常用注解1.1 AllArgsConstructor/NoArgsConstructor/RequiredArgsConstructor1.2 Builder1.3 Data1.4 EqualsAndHashCode1.5 Getter/Setter1.6 Slf4j/Log4j/Log4j2/Log1.7 ToString 二、踩坑2.1 Getter/Setter 方法名不一样2.2 Builder 不会生成无参构造方法2…...

uboot启动流程涉及reset函数

一. uboot启动流程中函数 之前了解了uboot链接脚本文件 u-boot.lds。 从 u-boot.lds 中我们已经知道了入口点是 arch/arm/lib/vectors.S 文件中的 _start。 本文了解 一下&#xff0c;uboot启动过程中涉及的 reset 函数。本文继上一篇文章学习&#xff0c;地址如下&#xff…...

端口被占用怎么解决

第一步&#xff1a;WinR 打开命令提示符&#xff0c;输入netstat -ano|findstr 端口号 找到占用端口的进程 第二步&#xff1a; 杀死使用该端口的进程&#xff0c;输入taskkill /t /f /im 进程号&#xff08; &#xff01;&#xff01;&#xff01;注意是进程号&#xff0c;不…...

python reportlab 生成多页pdf

多页 from reportlab.pdfgen import canvas from reportlab.platypus import (SimpleDocTemplate, Paragraph, PageBreak, Image, Spacer, Table, TableStyle) from reportlab.lib.enums import TA_LEFT, TA_RIGHT, TA_CENTER, TA_JUSTIFY from reportlab.lib.styles import P…...

word 多级目录的问题

一、多级标题自动编号 --> 制表符 -> 空格 网址&#xff1a; 【Word技巧】2 标题自动编号——将多级列表链接到样式 - YouTube 二、多级列表 --> 正规形式编号 网址&#xff1a;Word 教学 - 定框架&#xff1a;文档格式与多级标题&#xff01; - YouTube 三、目…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

Spring Boot面试题精选汇总

&#x1f91f;致敬读者 &#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 &#x1f4d8;博主相关 &#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...

相机Camera日志分析之三十一:高通Camx HAL十种流程基础分析关键字汇总(后续持续更新中)

【关注我,后续持续新增专题博文,谢谢!!!】 上一篇我们讲了:有对最普通的场景进行各个日志注释讲解,但相机场景太多,日志差异也巨大。后面将展示各种场景下的日志。 通过notepad++打开场景下的日志,通过下列分类关键字搜索,即可清晰的分析不同场景的相机运行流程差异…...

数据库分批入库

今天在工作中&#xff0c;遇到一个问题&#xff0c;就是分批查询的时候&#xff0c;由于批次过大导致出现了一些问题&#xff0c;一下是问题描述和解决方案&#xff1a; 示例&#xff1a; // 假设已有数据列表 dataList 和 PreparedStatement pstmt int batchSize 1000; // …...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;SCL 立刻变&#…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

云原生玩法三问:构建自定义开发环境

云原生玩法三问&#xff1a;构建自定义开发环境 引言 临时运维一个古董项目&#xff0c;无文档&#xff0c;无环境&#xff0c;无交接人&#xff0c;俗称三无。 运行设备的环境老&#xff0c;本地环境版本高&#xff0c;ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

LeetCode - 199. 二叉树的右视图

题目 199. 二叉树的右视图 - 力扣&#xff08;LeetCode&#xff09; 思路 右视图是指从树的右侧看&#xff0c;对于每一层&#xff0c;只能看到该层最右边的节点。实现思路是&#xff1a; 使用深度优先搜索(DFS)按照"根-右-左"的顺序遍历树记录每个节点的深度对于…...