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

数据结构与算法:二分查找(心得)

前言

前些天我做了一道题目,题目中要求使用二分查找,我便按照我心中的二分查找,信心满满的提交上去了。结果发现无限循环,后面我便去查阅了资料

 二分查找的条件

  1. 用于查找的内容需要是有序的
  2. 查找的数量只能是一个

 二分查找的二种方法

  1.  左闭右闭
  2. 左闭右开

二种用法区别就在于 

  1. while循环中 left 和 right 的关系,到底是 left <= right 还是 left < right
  2. 迭代过程中 middle 和 right 的关系,到底是 right = mid - 1 还是 right = mid

1. 左闭右闭

左闭右闭:每次查找的区间在[left, right],因为定义 target 在[left, right]区间,所以

  1. 循环条件要使用while(left <= right),因为当 left == right 这种情况发生的时候,得到的结果是有意义的
  2. if(arr[mid] > target) , right 要赋值为 mid - 1, 因为当前的 arr[mid] 一定不是 target ,那么接下来需要查找范围就是[left, mid - 1]
int search(int arr[], int size, int target) //size是数组的大小,target是需要查找的值
{int left = 0;int right = size - 1;	  // 定义了target在左闭右闭的区间内,[left, right]while (left <= right)     //当left == right时,区间[left, right]仍然有效{	int mid = left + ((right - left) / 2);//等同于 (left + right) / 2,防止溢出if (arr[mid] > target) {right = mid - 1;	  //target在左区间,所以[left, mid - 1]}else if (arr[mid] < target) {left = mid + 1;	      //target在右区间,所以[mid + 1, right]}else {	//既不在左边,也不在右边,那就是找到答案了return mid;}}//没有找到目标值return -1;
}

 2.左闭右开

左闭右开:每次查找的区间在 [left, right),条件控制应该如下:

  1. 循环条件使用while (left < right)
  2. if (arr[mid] > target), right = mid,因为当前的 arr[middle] 是大于 target 的,不符合条件,不能取到 mid,并且区间的定义是 [left, right),刚好区间上的定义就取不到 right, 所以 right 赋值为 mid。
int search(int arr[], int size, int target) //size是数组的大小,target是需要查找的值
{int left = 0;int right = size;	  while (left < right)     {	int mid = left + ((right - left) / 2);//等同于 (left + right) / 2,防止溢出if (arr[mid] > target) {right = mid;	  //target在左区间,所以[left, mid)}else if (arr[mid] < target) {left = mid + 1;	      //target在右区间,所以[mid + 1, right)}else {	//既不在左边,也不在右边,那就是找到答案了return mid;}}//没有找到目标值return -1;
}

 

这二种方法必须匹配使用循环条件和后续的区间赋值

 

 

 

 

相关文章:

数据结构与算法:二分查找(心得)

前言 前些天我做了一道题目&#xff0c;题目中要求使用二分查找&#xff0c;我便按照我心中的二分查找&#xff0c;信心满满的提交上去了。结果发现无限循环&#xff0c;后面我便去查阅了资料 二分查找的条件 用于查找的内容需要是有序的查找的数量只能是一个 二分查找的二种方…...

项目管理之分析项目特点的方法

在管理项目时&#xff0c;了解项目的目标和实现方法可以帮助我们更好地规划和执行项目。根据项目的目标和实现方法的不同&#xff0c;可以将项目分为四种类型&#xff1a;地、水、火和气。 对于工程项目&#xff0c;采用基于活动任务的计划管理方法&#xff0c;使用活动网络图…...

MyBatisPlus(二十一)乐观锁

使用场景 用于当有多个用户同时修改同一条数据的时候&#xff0c;只允许有一个修改成功。 实现原理 使用一个字段&#xff0c;用于记录数据的版本。 当修改数据时&#xff0c;会去检测当前版本是否是正在修改的版本&#xff0c;同时修改成功后会把 版本号 1。 实现方式 配…...

node 通过axios发送post请求(FormData)

方案一&#xff1a; const axios require(axios) const FormData require(form-data) const fs require(fs)const sdUpscaleOnAzure async (req, res) > {const data new FormData()data.append(image, fs.readFileSync(/temp/ai/sd/download/1.png))let config {hea…...

2024 王道考研-数据结构

第二章 线性表算法题(线性表的顺序表示) 二、综合应用题 01.从顺序表中删除具有最小值的元素(假设唯一)并由函数返回被删元素的值。空出的位 置由最后一个元素填补&#xff0c;若顺序表为空&#xff0c;则显示出错信息并退出运行。 算法思想&#xff1a;搜索整个顺序表&#xf…...

【疯狂Java讲义】Java学习记录(使用jar命令打包)

jar命令 把多个文件打包成一个压缩包——这个压缩包和WinZip的压缩格式是一样的。 区别在于jar压缩的文件默认多一个META-INF的文件夹&#xff0c;该文件夹里包含一个MANIFEST.MF的文件&#xff08;清单&#xff09;。 通常来说&#xff0c;得到的压缩包有3种&#xff08;压缩格…...

数据库第一、二章作业

只为记录与分享 第1,2章作业.xls 题量: 34 满分: 100 一. 单选题&#xff08;共34题&#xff09; 1. (单选题)在数据库中&#xff0c;下列说法&#xff08; &#xff09;是不正确的。 A. 数据库避免了一切数据的重复B. 若系统是完全可以控制的&#xff0c;则系统可确保更新…...

将数组拆分成斐波那契序列

题目描述 示例 代码如下&#xff1a; public class SplitIntoFibonacci {LinkedList<Integer> res new LinkedList<>();public List<Integer> splitIntoFibonacci(String num) {if(num.length() < 3) return res;if(dfs(num, 0)) return res;return new…...

【Linux】:权限

朋友们、伙计们&#xff0c;我们又见面了&#xff0c;本期来给大家解读一下有关Linux的基础知识点&#xff0c;如果看完之后对你有一定的启发&#xff0c;那么请留下你的三连&#xff0c;祝大家心想事成&#xff01; C 语 言 专 栏&#xff1a;C语言&#xff1a;从入门到精通 数…...

8年软件测试工程师感悟——写给还在迷茫中的朋友

这两天和朋友谈到软件测试的发展&#xff0c;其实软件测试已经在不知不觉中发生了非常大的改变&#xff0c;前几年的软件测试行业还是一个风口&#xff0c;随着不断地转行人员以及毕业的大学生疯狂地涌入软件测试行业&#xff0c;目前软件测试行业“缺口”已经基本饱和。当然&a…...

CleanMyMac苹果电脑清理软件是智商税吗?最全评测价格、清理效果一次说清

这是一篇CleanMyMac最全评测&#xff01;价格、清理效果一次说清&#xff0c;告诉你它真不是智商税! 升级Ventura系统之前&#xff0c;我用的是CleanMyMac X绿色版&#xff08;绝不提倡这个行为&#xff09;。更新到Ventura之后&#xff0c;之前很多绿色软件失效&#xff0c;浪…...

【pytorch 中 torch.max 和 torch.argmax 的区别】

torch.max 和 torch.argmax 的区别 1.torch.max torch.max(input, dim, maxNone, max_indicesNone, keepdimFalse) -->> (Tensor, LongTensor) 作用&#xff1a;找出给定tensor的指定维度dim上的上的最大值&#xff0c;并返回最大值在该维度上的值和位置索引。 应用举…...

无效的 page.json [“window“] 页面.json配置了“window“: {“disableScroll“: true}

问题&#xff1a;启动小程序时报错 无效的 page.json ["window"] 页面 解决&#xff1a; app.json 全局配置才使用window对象&#xff0c;在单独的页面直接写disableScroll:true即可 //app.json中添加&#xff0c;window里面添加就可以了 "window": { …...

2023最新短视频配音软件~

随着互联网的迅猛发展&#xff0c;网络平台上的影视剧配音逐渐成为一种热门赚钱方式。那么&#xff0c;想要参与影视剧配音赚钱&#xff0c;就需要拥有一款好用的配音软件。下面我就为大家介绍一款最新的影视剧配音神器&#xff01; 悦音配音 这是一款大家都在用的配音工具&am…...

【内网击穿工具 】NATAPP

内网穿透又叫内网映射&#xff0c;功能是把内网IP映射到公网&#xff0c;使公网也能轻松访问所搭建的服务。 内网与外网 外网指的是一个组织或网络中可公开访问的网络&#xff0c;即对外开放的网络。外网可以通过公共互联网进行访问 内网是相对于外网而言的&#xff0c;指的…...

vue 使用crypto.js解密后,用JSON.parse转义报错非空白格解决办法

问题&#xff1a; 用JSON.parse转义crypto解密后的json字符串会发生错误。如图&#xff1a; 原因&#xff1a; 那是因为crypto自己加了一些未可见的字符&#xff0c;所以用正常的JSON.parse(xxxx)会报错。 解决办法&#xff1a; JSON.parse(xxxx.replace(/[\u0000-\u001F\u…...

全景分割的自监督学习

在本章中,我们将第3章中讨论的SSL方法扩展到语义和全景分割任务。使用手动生成的标签训练的卷积神经网络通常用于语义或实例分割。 在精准农业中,自动化花朵检测方法使用监督模型和后处理技术,随着花朵的外观和数据采集条件的变化,这些技术可能无法始终如一地执行。我们提…...

基于python的23种设计模式

以下是基于Python实现的23种设计模式及代码段和详细解释&#xff1a; 1. 工厂模式&#xff08;Factory Pattern&#xff09; 简介 工厂模式是一种创建型设计模式&#xff0c;它允许客户端代码通过工厂方法创建对象&#xff0c;而无需直接实例化对象。在工厂方法模式中&#…...

屏幕录制视频编辑软件 Camtasia 2023 mac中文版软件功能

Camtasia 2023 mac是一款功能强大的屏幕录制和视频编辑软件&#xff0c;可以用于制作教育课程、演示文稿、培训视频等。它具有一系列工具和功能&#xff0c;包括屏幕录制、视频编辑、音频编辑、字幕、特效等&#xff0c;使用户可以轻松地创建高质量的视频内容。 Camtasia2023的…...

关于spring的xml文件中的xmlns,xsi,schemaLocation

关于spring xml文件中的xmlns,xsi:schemaLocation 首先我们看到的一个spring的配置文件大概如下面这个样子&#xff1a; <?xml version"1.0" encoding"UTF-8"?> <beans xmlns"http://www.springframework.org/schema/beans" //这表…...

idea大量爆红问题解决

问题描述 在学习和工作中&#xff0c;idea是程序员不可缺少的一个工具&#xff0c;但是突然在有些时候就会出现大量爆红的问题&#xff0c;发现无法跳转&#xff0c;无论是关机重启或者是替换root都无法解决 就是如上所展示的问题&#xff0c;但是程序依然可以启动。 问题解决…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

【单片机期末】单片机系统设计

主要内容&#xff1a;系统状态机&#xff0c;系统时基&#xff0c;系统需求分析&#xff0c;系统构建&#xff0c;系统状态流图 一、题目要求 二、绘制系统状态流图 题目&#xff1a;根据上述描述绘制系统状态流图&#xff0c;注明状态转移条件及方向。 三、利用定时器产生时…...

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别

OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

基于IDIG-GAN的小样本电机轴承故障诊断

目录 🔍 核心问题 一、IDIG-GAN模型原理 1. 整体架构 2. 核心创新点 (1) ​梯度归一化(Gradient Normalization)​​ (2) ​判别器梯度间隙正则化(Discriminator Gradient Gap Regularization)​​ (3) ​自注意力机制(Self-Attention)​​ 3. 完整损失函数 二…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...

群晖NAS如何在虚拟机创建飞牛NAS

套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...

零知开源——STM32F103RBT6驱动 ICM20948 九轴传感器及 vofa + 上位机可视化教程

STM32F1 本教程使用零知标准板&#xff08;STM32F103RBT6&#xff09;通过I2C驱动ICM20948九轴传感器&#xff0c;实现姿态解算&#xff0c;并通过串口将数据实时发送至VOFA上位机进行3D可视化。代码基于开源库修改优化&#xff0c;适合嵌入式及物联网开发者。在基础驱动上新增…...