当前位置: 首页 > 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 代码&…...

像素艺术×AI识别:Ostrakon-VL扫描终端CSS修复实战详解

像素艺术AI识别&#xff1a;Ostrakon-VL扫描终端CSS修复实战详解 1. 项目背景与设计理念 1.1 为什么选择像素艺术风格 在零售和餐饮场景中&#xff0c;传统的工业级UI往往显得冰冷且缺乏亲和力。我们选择8-bit像素艺术风格&#xff0c;主要基于三个考量&#xff1a; 降低技…...

多语言翻译工作流:OpenClaw协同千问3.5-27B实现文档自动本地化

多语言翻译工作流&#xff1a;OpenClaw协同千问3.5-27B实现文档自动本地化 1. 为什么需要智能翻译流水线&#xff1f; 去年参与一个开源项目时&#xff0c;我遇到了文档翻译的噩梦。团队需要将技术文档同步翻译成英、日、韩三种语言&#xff0c;传统流程是&#xff1a;先用机…...

SEO优化的预算一般应如何合理安排

SEO优化的预算一般应如何合理安排 在当今数字化时代&#xff0c;网站的搜索引擎优化&#xff08;SEO&#xff09;已成为提升网站流量和品牌知名度的重要手段。如何合理分配SEO优化预算成为许多企业和网站管理者面临的一个重要课题。本文将从问题分析、原因说明、解决方法、注意…...

从ROS Bag到标定矩阵:Livox Mid-360多雷达数据预处理全流程详解(含CustomMsg转PCD脚本)

Livox Mid-360多雷达数据预处理实战&#xff1a;从原始数据到标定就绪的完整指南 在自动驾驶和机器人感知系统中&#xff0c;多激光雷达的协同工作已成为提升环境感知能力的标配方案。Livox Mid-360凭借其独特的非重复扫描模式和360水平视场&#xff0c;为复杂环境下的三维重建…...

终极图像纹理合成工具:GIMP Resynthesizer 完整使用指南

终极图像纹理合成工具&#xff1a;GIMP Resynthesizer 完整使用指南 【免费下载链接】resynthesizer Suite of gimp plugins for texture synthesis 项目地址: https://gitcode.com/gh_mirrors/re/resynthesizer GIMP Resynthesizer 是一套功能强大的 GIMP 纹理合成插件…...

3DGS内存优化新思路:拆解Scaffold-GS与Normal-GS中的锚点与共享IDIV设计

3DGS内存优化新思路&#xff1a;拆解Scaffold-GS与Normal-GS中的锚点与共享IDIV设计 在实时3D渲染领域&#xff0c;3D Gaussian Splatting&#xff08;3DGS&#xff09;技术正面临内存效率的严峻挑战。当我们将3DGS模型部署到移动设备或边缘计算节点时&#xff0c;显存限制往往…...

基于深度学习的多种类动物识别(YOLOv12/v11/v8/v5模型+数据集)(源码+lw+部署文档+讲解等)

摘要随着人工智能和深度学习技术的发展&#xff0c;基于图像的动物识别系统在生态监测、物种保护和生物多样性研究等领域获得了广泛应用。本文提出了一种基于YOLO&#xff08;You Only Look Once&#xff09;系列模型&#xff08;包括YOLOv5、YOLOv8、YOLOv11和YOLOv12&#xf…...

【Axure教程】字母定位选择器

今天教大家用一个中继器制作字母分类定位选择器的原型模板&#xff0c;模版我们用中继器制作的&#xff0c;所以使用也很方便&#xff0c;只需要在中继器表格对应位置填写选项信息&#xff0c;即可自动生成交互效果&#xff0c;具体效果可以打开下方预览地址体验。 【原型效果…...

5步突破:思源宋体TTF字体库的商业级应用方案

5步突破&#xff1a;思源宋体TTF字体库的商业级应用方案 【免费下载链接】source-han-serif-ttf Source Han Serif TTF 项目地址: https://gitcode.com/gh_mirrors/so/source-han-serif-ttf 还在为中文排版的专业性发愁吗&#xff1f;面对商业字体高昂的授权费用和免费字…...

CSS遮罩艺术:从基础阴影到高级毛玻璃特效实战

1. 从零开始理解CSS遮罩 遮罩效果在前端开发中就像给界面元素戴上了一层"面纱"。想象一下&#xff0c;当你需要突出某个弹窗内容时&#xff0c;背后的页面会变暗——这就是最常见的遮罩应用场景。我们先从最基础的实现方式说起。 基础遮罩的实现通常需要一个覆盖全…...