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

手撕数据结构02--二分搜索(附源码)

一、理论基础

二分搜索,也称折半搜索、对数搜索,是一种在有序数组中查找某一特定元素的搜索算法。

二分搜索是一种高效的查找算法,适用于在已排序的数组中查找特定元素。它的基本思想是通过不断将搜索区间对半分割,从而快速缩小查找范围。

二分搜索每次把搜索区域减少一半,时间复杂度为 O(logn)(n代表集合中元素的个数)。

二分搜索的基本步骤如下:

1.初始条件:将搜索范围设为数组的整个区间。
2.查找中间元素:计算当前区间的中间索引。
3.比较中间元素:将中间元素与目标值进行比较:

  • 如果中间元素等于目标值,查找成功,返回中间索引。
  • 如果中间元素小于目标值,将搜索范围缩小到右半部分。
  • 如果中间元素大于目标值,将搜索范围缩小到左半部分。

4.重复步骤 2 和 3,直到找到目标值或搜索范围为空。


在下图中为大家展示了二分搜索的过程:

二、代码实现

#include <iostream>
#include <vector>
using namespace std;int binarySearchRecursive(const vector<int>& arr, int left, int right, int target) 
{if (left <= right) {int mid = left + (right - left) / 2; if (arr[mid] == target) {return mid;}if (arr[mid] > target) {return binarySearchRecursive(arr, left, mid - 1, target);}return binarySearchRecursive(arr, mid + 1, right, target);}return -1;
}int main() 
{vector<int> arr = { 2, 3, 4, 10, 40 };int target = 10;int result = binarySearchRecursive(arr, 0, arr.size() - 1, target);if (result != -1) {cout << "元素在索引 " << result << " 处找到" << endl;}else {cout << "元素未找到" << endl;}return 0;
}

相关文章:

手撕数据结构02--二分搜索(附源码)

一、理论基础 二分搜索&#xff0c;也称折半搜索、对数搜索&#xff0c;是一种在有序数组中查找某一特定元素的搜索算法。 二分搜索是一种高效的查找算法&#xff0c;适用于在已排序的数组中查找特定元素。它的基本思想是通过不断将搜索区间对半分割&#xff0c;从而快速缩小…...

单片机工程师继续从事硬件设计还是涉足 Linux 开发?

在开始前刚好我有一些资料&#xff0c;是我根据网友给的问题精心整理了一份「linux的资料从专业入门到高级教程」&#xff0c;点个关注在评论区回复“666”之后私信回复“666”&#xff0c;全部无偿共享给大家&#xff01;&#xff01;&#xff01; 怎么说呢&#xff0c;感觉绝…...

《昇思25天学习打卡营第25天|第28天》

今天是打卡的第二十八天&#xff0c;实践应用篇中的计算机视觉中Vision Transformer图像分类。 从Vision Transformer&#xff08;ViT&#xff09;简介开始了解&#xff0c;模型结构&#xff0c;模型特点&#xff0c;实验的环境准备和数据读取&#xff0c;模型解析&#xff08…...

Flutter Dio网络请求报错FormatException: Unexpected character

最近开发Flutter项目&#xff0c;网络请求采用的是Dio框架&#xff0c;在发起网络请求的时候报错&#xff1a; 网络请求返回的数据为&#xff1a; var returnCitySN {"cip": "127.0.0.1", "cid": "00", "cname": "未…...

关于@JsonSerialize序列化与@JsonDeserialize反序列化注解的使用(密码加密与解密举例)

注&#xff1a;另一种方式参考 关于TableField中TypeHandler属性&#xff0c;自定义的类型处理器的使用&#xff08;密码加密与解密举例&#xff09;http://t.csdnimg.cn/NZy4G 1.简介 1.1 序列化与反序列化 学习注解之前&#xff0c;我们可以先了解一下什么是序列化与反序列…...

第二届世界科学智能大赛逻辑推理赛道:复杂推理能力评估 #大模型技术之逻辑推理方向 #Datawhale #夏令营 <二>

第二届世界科学智能大赛逻辑推理赛道&#xff1a;复杂推理能力评估 #大模型技术之逻辑推理方向 #Datawhale #夏令营-CSDN博客 这里在上一篇的基础上&#xff0c;已经充分理解了一遍baseline的流程&#xff0c;并修复了一些后处理的问题&#xff0c;包括答案抽取&#xff0c;中间…...

C# 关于Linq延迟查询

demo: int Count 0;string[] obj { "item1", "item2", "item3", "item4", "item5", "item6" };var query obj.Where(item > IsTrue(item));// 第一次遍历foreach (var item in query){Console.WriteLine(it…...

Navicat For Mysql连接Mysql8.0报错:客户端不支持服务器请求的身份验证协议

windows通过navicat连接本地mysql时报错:Client does not support authentication protocol requested by server; consider upgrading MySQL client 一、问题原因二、解决方法1--失败1. 连接mysql客户端2. 修改加密方式3.正确的解决方法1.查找my.ini文件2.修改my.ini文件3.重…...

以西门子winCC为代表的组态界面,还是有很大提升空间的。

组态界面向来都是功能为主&#xff0c;美观和体验性为辅的&#xff0c;这也导致了国内的一些跟随者如法炮制&#xff0c;而且很多操作的工程师也是认可这重模式&#xff0c;不过现在一些新的组态软件可是支持精美的定制化界面&#xff0c;还有3D交互效果&#xff0c;这就是确实…...

HomeServer平台选择,介绍常用功能

​​ 平台选择 HomeServer 的性能要求不高&#xff0c;以下是我的硬件参数&#xff0c;可供参考&#xff1a; ‍ 硬件&#xff1a; 平台&#xff1a;旧笔记本CPU&#xff1a;i5 4210u内存 8G硬盘&#xff1a;128G 固态做系统盘&#xff0c;1T1T 机械盘组 RAID1 做存储。硬…...

记录一个k8s集群zookeeper部署过程

由于网管中心交维要求必须是支持高可用配置&#xff0c;原先单节点的zookeeper不被允许。所以在k8s集群中做了一个高可用版本的zookeeper。 期间有点小波折&#xff0c;官方给的镜像版本太老&#xff0c;业务不支持&#xff0c;所以手动做了下处理&#xff0c;重新打了一个镜像…...

TapData 信创数据源 | 国产信创数据库 TiDB 数据迁移指南,加速国产化进程,推进自主创新建设

随着国家对自主可控的日益重视&#xff0c;目前在各个行业和区域中面临越来越多的国产化&#xff0c;采用有自主知识产权的国产数据库正在成为主流。长期以来&#xff0c;作为拥有纯国产自研背景的 TapData&#xff0c;自是非常重视对于更多国产信创数据库的数据连接器支持&…...

开始写人工智能

文章目录 概述 概述 开始写人工智能模块。既然决定开始写这些&#xff0c;那就开始吧&#xff01;...

盘点.软件测试模型

软件开发模型   软件开发模型(Software Development Model)是指软件开发全部过程、活动和任务的结构框架。软件开发包括需求、设计、编码和测试等阶段&#xff0c;有时也包括维护阶段。 软件开发模型能清晰、直观地表达软件开发全过程&#xff0c;明确规定了要完成的主要活动…...

燃气安全无小事,一双专业劳保鞋让你步步安心!

燃气作为我们日常生活中不可或缺的能源之一&#xff0c;为我们的生活提供了极大便利&#xff0c;其安全性往往被忽视在忙碌的日常生活背后。然而&#xff0c;燃气事故一旦发生&#xff0c;后果往往不堪设想&#xff0c;轻则财产损失&#xff0c;重则危及生命。因此&#xff0c;…...

springboot校园服装租赁系统-计算机毕业设计源码30824

目 录 摘要 1 绪论 1.1 研究背景与意义 1.2国内外研究现状 1.3论文结构与章节安排 2 校园服装租赁系统分析 2.1 可行性分析 2.1.1 技术可行性分析 2.1.2 经济可行性分析 2.1.3 法律可行性分析 2.2 系统功能分析 2.2.1 功能性分析 2.2.2 非功能性分析 2.3 系统用例…...

线性回归和逻辑回归揭示数据的隐藏模式:理论与实践全解析

机器学习之线性回归和逻辑回归 1. 简介1.1 机器学习概述1.2 监督学习的定义与重要性1.3 线性回归和逻辑回归在监督学习中的作用1.3.1 线性回归1.3.2 逻辑回归 2. 线性回归&#xff08;Linear Regression&#xff09;2.1 定义与目标2.1.1 回归问题的定义2.1.2 预测连续目标变量 …...

掌握采购询价软件:高效比较供应商报价的技巧

在企业运营中&#xff0c;获取所需的产品往往是一项复杂且耗时的任务&#xff0c;这涉及多个环节和流程。然而&#xff0c;借助电子采购询价&#xff08;RFQ&#xff09;系统&#xff0c;许多原本需要采购员手动完成的任务可以自动化运行&#xff0c;从而提高了效率。 那么问题…...

AMQP-核心概念-终章

本文参考以下链接摘录翻译&#xff1a; https://www.rabbitmq.com/tutorials/amqp-concepts 连接&#xff08;Connections&#xff09; AMQP 0-9-1连接通常是长期保持的。AMQP 0-9-1是一个应用级别的协议&#xff0c;它使用TCP来实现可靠传输。连接使用认证且可以使用TLS保护…...

在WPF中使用WebView2详解

Microsoft Edge WebView2 Microsoft Edge WebView2 控件允许在本机应用中嵌入 web 技术(HTML、CSS 以及 JavaScript)。 WebView2 控件使用 Microsoft Edge 作为绘制引擎&#xff0c;以在本机应用中显示 web 内容。 使用 WebView2 可以在本机应用的不同部分嵌入 Web 代码&…...

效率提升秘籍,用快马平台生成模块化openclaw配置代码

在深度学习项目中&#xff0c;模型配置往往是开发过程中最耗时的环节之一。最近我在尝试构建一个openclaw模型时&#xff0c;发现通过InsCode(快马)平台可以大幅提升效率&#xff0c;今天就分享一下我的实践心得。 模块化设计思路 传统模型开发中&#xff0c;我们经常需要反复编…...

终极指南:3个简单步骤免费下载B站4K大会员视频

终极指南&#xff1a;3个简单步骤免费下载B站4K大会员视频 【免费下载链接】bilibili-downloader B站视频下载&#xff0c;支持下载大会员清晰度4K&#xff0c;持续更新中 项目地址: https://gitcode.com/gh_mirrors/bil/bilibili-downloader 你是否曾遇到过这样的场景&…...

微信小程序框架详解

小程序包含一个描述整体程序的app实例和多个描述页面的page。其中app由三个文件构成:公共配置app.json、公共样式app.wxss、主体逻辑app.js。每个page最多由四个文件构成:页面配置page.json、页面结构page.wxml、页面样式page.wxss、页面主体逻辑page.js。 微信小程序的主体部…...

React Notion X安全配置终极指南:防止XSS攻击与数据泄露的10个关键策略

React Notion X安全配置终极指南&#xff1a;防止XSS攻击与数据泄露的10个关键策略 【免费下载链接】react-notion-x Fast and accurate React renderer for Notion. TS batteries included. ⚡️ 项目地址: https://gitcode.com/gh_mirrors/re/react-notion-x React No…...

OpenClaw硬件监控:Gemma-3-12b-it分析传感器数据并预警

OpenClaw硬件监控&#xff1a;Gemma-3-12b-it分析传感器数据并预警 1. 为什么需要AI驱动的硬件监控&#xff1f; 去年夏天&#xff0c;我的家用服务器因为CPU散热器故障导致过热关机&#xff0c;丢失了正在处理的科研数据。这件事让我开始思考&#xff1a;传统的阈值告警太被…...

OpenClaw性能调优:降低Phi-3-mini-128k-instruct长任务token消耗的技巧

OpenClaw性能调优&#xff1a;降低Phi-3-mini-128k-instruct长任务token消耗的技巧 1. 问题背景&#xff1a;长任务带来的token消耗困境 上周我在用OpenClaw处理一个文档整理任务时&#xff0c;遇到了一个棘手的问题。这个任务需要读取50多份Markdown格式的技术文档&#xff…...

大数据领域HBase的备份与恢复方案

大数据领域HBase的备份与恢复方案 关键词&#xff1a;HBase备份恢复、分布式存储、数据持久化、全量备份、增量备份、灾难恢复、快照机制 摘要&#xff1a;本文系统解析HBase分布式环境下的数据备份与恢复技术体系&#xff0c;涵盖核心存储原理、多维度备份策略&#xff08;全量…...

硬件工程师的福音:用Beyond Compare 4表格比对功能,5分钟搞定BOM清单版本差异检查

硬件工程师的效率革命&#xff1a;Beyond Compare 4表格比对功能深度解析 在硬件研发的日常工作中&#xff0c;BOM清单的版本管理往往是最令人头疼的环节之一。每次PCB设计的小版本迭代——无论是物料替换、数量调整还是参数优化——都需要工程师花费大量时间核对变更细节。传统…...

STM32精准延时实现与Keil调试技巧

1. 精准延时在单片机开发中的重要性在STM32等嵌入式系统开发中&#xff0c;精准延时是基础但至关重要的功能。我最近调试一块自制的STM32开发板时&#xff0c;就遇到了需要精确控制时序的场景。比如在驱动LCD屏幕时&#xff0c;某些控制信号需要维持15ms的精确延时&#xff0c;…...

当AI真正“看懂“你的屏幕:GPT-5.4如何重新定义人机协作的边界

摘要&#xff1a; 2026年3月&#xff0c;OpenAI发布了GPT-5.4。这不是一次普通的模型迭代&#xff0c;而是一次能力边界的重新定义——它首次实现了原生的"计算机使用"能力&#xff0c;能在桌面上像人类一样点击按钮、填写表单、操作软件&#xff1b;它拥有五级可调的…...