《二分查找算法:在有序数组中搜索目标值》
目录
一、问题分析
二、二分查找算法原理
三、代码实现
给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target,我们要写一个函数来搜索 nums 中的 target,如果目标值存在就返回它的下标,否则返回 -1。
一、问题分析
既然数组是有序的,那么我们自然而然地会想到一种高效的查找算法 —— 二分查找(Binary Search)。二分查找的基本思想是将查找区间不断缩小一半,直到找到目标元素或者确定目标元素不存在为止。
二、二分查找算法原理
- 首先,我们确定查找区间的左右边界。初始时,左边界
left为 0,右边界right为数组的长度n - 1。 - 然后,在每一轮查找中,我们计算中间元素的下标
mid,计算公式为mid = left + (right - left) // 2。这里使用left + (right - left) // 2而不是简单的(left + right) // 2是为了避免在left和right很大时出现整数溢出的情况。 - 接下来,我们比较中间元素
nums[mid]和目标值target:- 如果
nums[mid] == target,那么我们就找到了目标值,直接返回mid即可。 - 如果
nums[mid] < target,这说明目标值在中间元素的右侧,我们就将左边界left更新为mid + 1,继续在右侧区间进行查找。 - 如果
nums[mid] > target,这说明目标值在中间元素的左侧,我们就将右边界right更新为mid - 1,继续在左侧区间进行查找。
- 如果
- 不断重复上述步骤,直到左边界
left大于右边界right,这时候就说明目标值不存在于数组中,我们返回 -1。
三、代码实现
class Solution {public int search(int[] nums, int target) {int left = 0;int right = nums.length-1;while(left<=right){int mid = (left+right)/2;if(nums[mid]==target){//相等 找到啦return mid;}else if(nums[mid]<target){left = mid+1;}else{//目标值小right = mid-1;}}//没找到return -1;}
}
相关文章:
《二分查找算法:在有序数组中搜索目标值》
目录 一、问题分析 二、二分查找算法原理 三、代码实现 给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target,我们要写一个函数来搜索 nums 中的 target,如果目标值存在就返回它的下标,否则返回 -1。 …...
【万字总结】数据结构常考应用大题做法画法详解_树_哈希表_图_排序大总结
文章目录 1.树相关应用大题1.1 已知二叉树的中序序列和前序or中序,画出二叉树1.2 二叉树的遍历、树的遍历、森林的遍历总结1.3二叉树与森林之间的转换1.3.1 已知树的先序序列和中序序列,画出森林 1.4 二叉树的线索化1.5 二叉排序树1.5.1 二叉排序树的删除…...
Docker + Jenkins + gitee 实现CICD环境搭建
目录 前言 关于Jenkins 安装Jenkins docker中运行Jenkins注意事项 通过容器中的Jenkins,把服务打包到docker进行部署 启动Jenkins 创建第一个任务 前言 CI/CD(持续集成和持续交付/持续部署),它可以实现自动化的构建、测试和部署…...
rabbitMq怎么保证消息不丢失?消费者没有接收到消息怎么处理
在使用RabbitMQ时,保证消息不丢失以及处理消费者未接收到消息的情况可以通过以下几个方法: 1. 确保消息的持久化 队列持久化:在声明队列时将其设置为持久化(durabletrue),这样RabbitMQ在重启后也会保留队…...
商务数据分析在提升客户体验方面的作用体现在哪些环节
在当今竞争激烈的商业环境中,客户体验已成为企业成功的关键因素。商务数据分析犹如一把神奇的钥匙,在提升客户体验的征程中发挥着至关重要的作用,贯穿于多个环节。 一、客户需求分析:洞察客户内心的窗口 客户需求分析是商务数据…...
cooladmin使用整理
1、后端关键字自动生成没有代码段提示,原因是拉取的项目代码中没有.vscode文件夹,复制一套至项目src同级即可 2、前端快速创建,在Entity完成后就去快速创建中选数据结构,这时没有对应的内容,数据结构是和controller层a…...
CentOS 7 更换软件仓库
CentOS 7 于2024年6月30日停止维护,官方仓库已经没有软件了,想要继续使用 ,需要更换软件仓库,这里更换到阿里云的软件仓库 https://developer.aliyun.com/mirror/ 查看目前可用的软件数量 yum repolist 更换软件仓库:…...
现代Web开发:React Hooks深入解析
💓 博客主页:瑕疵的CSDN主页 📝 Gitee主页:瑕疵的gitee主页 ⏩ 文章专栏:《热点资讯》 现代Web开发:React Hooks深入解析 现代Web开发:React Hooks深入解析 现代Web开发:React Hook…...
HarmonyOS使用arkTS拉起指定第三方应用程序
HarmonyOS使用arkTS拉起指定第三方应用程序 前言代码及说明bundleName获取abilityName获取 前言 本篇只说采用startAbility方式拉起第三方应用,需要用到两个必备的参数bundleName,abilityName,本篇就介绍如何获取参数… 代码及说明 bundle…...
flex安装学习笔记
https://zhuanlan.zhihu.com/p/2783726096 3.下载 Flux 模型 FLUX.1 [dev] :官方版本满配版,最低显存要求 24G;FLUX.1 [dev] fp8:大佬优化 [dev] 后版本,建议选择此版本,最低 12G 显存可跑;FLU…...
09-结构化搜索、搜索的相关性算分
term 查询执行精确值匹配,要求文档中的字段值与指定的词项完全相等。对于日期字段等精确值字段,通常使用 term 查询可以快速有效地匹配文档。match 查询执行全文搜索,会对输入的文本进行分析,生成查询词项,并试图找到与…...
手机屏幕上进行OCR识别方案
在手机屏幕上进行OCR识别,可以通过一些主流方案实现高效、准确的文本识别。以下是几种常见方案: 1. 使用 Tesseract OCR 原理:Tesseract 是一个开源的 OCR 引擎,支持多种语言。可以通过一些优化提升其对手机屏幕文本的识别效果。…...
遗传算法与深度学习实战(22)——使用Numpy构建神经网络
遗传算法与深度学习实战(22)——使用Numpy构建神经网络 0. 前言1. 神经网络基础1.1 简单神经网络的架构1.2 神经网络的训练 2. 使用 Numpy 构建神经网络2.1 网络架构2.2 实现神经网络 小结系列链接 0. 前言 我们已经学习了如何使用进化算法来优化深度学…...
react->Antd->Table调整checkbox默认样式
checkbox默认不展示,hover此行时,出现checkbox,选中后不消失: hover前,设置透明边框; hover时,checkbox出现 选中后 代码块: .ant-checkbox {.ant-checkbox-inner {border: transparent;}}.ant…...
一种ESB的设计
系统架构 ESB包括: ESB总控服务、业务应用集群、业务消息WEB服务、业务消息日志服务、运维管理平台、业务设计器。如下图所示 ESB总控服务 ESB总控服务承载了各项业务的运维和管理。主要包括: 业务流程的管理ESB内部不同模块间的通讯ESB系统设置和管理…...
上位机常用通信方式
1. 串口通信:RS232(设备和PC之间,最常用,短距离)、RS485(工业现场总线,长距离,多点通信) 2. 以太网通信:TCP/IP协议 3. CAN总线通信 4. Modbus协议࿱…...
Vue3中使用LogicFlow实现简单流程图
实现结果 实现功能: 拖拽创建节点自定义节点/边自定义快捷键人员选择弹窗右侧动态配置组件配置项获取/回显必填项验证 自定义节点与拖拽创建节点 拖拽节点面板node-panel.vue <template><div class"node-panel"><divv-for"(item, k…...
《重学Java设计模式》之 工厂方法模式
《重学Java设计模式》之 建造者模式 《重学Java设计模式》之 原型模式 《重学Java设计模式》之 单例模式 模拟发奖多种商品 工程结构 奖品发放接口 package com.yys.mes.design.factory.store;public interface ICommodity {/*** Author Sherry* Date 14:20 2024/11/6**/voi…...
【大数据学习 | kafka】kafka的数据存储结构
以上是kafka的数据的存储方式。 这些数据可以在服务器集群上对应的文件夹中查看到。 [hexuanhadoop106 __consumer_offsets-0]$ ll 总用量 8 -rw-rw-r--. 1 hexuan hexuan 10485760 10月 28 22:21 00000000000000000000.index -rw-rw-r--. 1 hexuan hexuan 0 10月 28 …...
知识竞赛答题系统,线上答题小程序链接怎么做?
随着智能手机的普及,越来越多的单位开始在线上开展知识竞赛。这种形式的知识竞赛不仅易于操作,而且参与度更高。那么线上知识竞赛答题系统怎么做呢?自己可以做吗?答案是可以的!借助微信答题系统制作平台风传吧…...
未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?
编辑:陈萍萍的公主一点人工一点智能 未来机器人的大脑:如何用神经网络模拟器实现更智能的决策?RWM通过双自回归机制有效解决了复合误差、部分可观测性和随机动力学等关键挑战,在不依赖领域特定归纳偏见的条件下实现了卓越的预测准…...
【Python】 -- 趣味代码 - 小恐龙游戏
文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
VB.net复制Ntag213卡写入UID
本示例使用的发卡器:https://item.taobao.com/item.htm?ftt&id615391857885 一、读取旧Ntag卡的UID和数据 Private Sub Button15_Click(sender As Object, e As EventArgs) Handles Button15.Click轻松读卡技术支持:网站:Dim i, j As IntegerDim cardidhex, …...
ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
MySQL用户和授权
开放MySQL白名单 可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务: test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...
C# 表达式和运算符(求值顺序)
求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如,已知表达式3*52,依照子表达式的求值顺序,有两种可能的结果,如图9-3所示。 如果乘法先执行,结果是17。如果5…...
Git常用命令完全指南:从入门到精通
Git常用命令完全指南:从入门到精通 一、基础配置命令 1. 用户信息配置 # 设置全局用户名 git config --global user.name "你的名字"# 设置全局邮箱 git config --global user.email "你的邮箱example.com"# 查看所有配置 git config --list…...
LangFlow技术架构分析
🔧 LangFlow 的可视化技术栈 前端节点编辑器 底层框架:基于 (一个现代化的 React 节点绘图库) 功能: 拖拽式构建 LangGraph 状态机 实时连线定义节点依赖关系 可视化调试循环和分支逻辑 与 LangGraph 的深…...
二维FDTD算法仿真
二维FDTD算法仿真,并带完全匹配层,输入波形为高斯波、平面波 FDTD_二维/FDTD.zip , 6075 FDTD_二维/FDTD_31.m , 1029 FDTD_二维/FDTD_32.m , 2806 FDTD_二维/FDTD_33.m , 3782 FDTD_二维/FDTD_34.m , 4182 FDTD_二维/FDTD_35.m , 4793...
