当前位置: 首页 > 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" //这表…...

AI-调查研究-01-正念冥想有用吗?对健康的影响及科学指南

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

微信小程序 - 手机震动

一、界面 <button type"primary" bindtap"shortVibrate">短震动</button> <button type"primary" bindtap"longVibrate">长震动</button> 二、js逻辑代码 注&#xff1a;文档 https://developers.weixin.qq…...

SpringBoot+uniapp 的 Champion 俱乐部微信小程序设计与实现,论文初版实现

摘要 本论文旨在设计并实现基于 SpringBoot 和 uniapp 的 Champion 俱乐部微信小程序&#xff0c;以满足俱乐部线上活动推广、会员管理、社交互动等需求。通过 SpringBoot 搭建后端服务&#xff0c;提供稳定高效的数据处理与业务逻辑支持&#xff1b;利用 uniapp 实现跨平台前…...

【android bluetooth 框架分析 04】【bt-framework 层详解 1】【BluetoothProperties介绍】

1. BluetoothProperties介绍 libsysprop/srcs/android/sysprop/BluetoothProperties.sysprop BluetoothProperties.sysprop 是 Android AOSP 中的一种 系统属性定义文件&#xff08;System Property Definition File&#xff09;&#xff0c;用于声明和管理 Bluetooth 模块相…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

图表类系列各种样式PPT模版分享

图标图表系列PPT模版&#xff0c;柱状图PPT模版&#xff0c;线状图PPT模版&#xff0c;折线图PPT模版&#xff0c;饼状图PPT模版&#xff0c;雷达图PPT模版&#xff0c;树状图PPT模版 图表类系列各种样式PPT模版分享&#xff1a;图表系列PPT模板https://pan.quark.cn/s/20d40aa…...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...