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

【二分查找】朴素二分查找

二分查找

题目描述

给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示:

  1. 你可以假设 nums 中的所有元素是不重复的。
  2. n 将在 [1, 10000]之间。
  3. nums 的每个元素都将在 [-9999, 9999]之间。

核心算法

朴素二分查找算法

  • x < t -> left = mid + 1 [left, right]
  • x > t -> right = mid - 1 [left, right]
  • x == t 返回结果

细节问题

  1. 循环结束的条件

    left > right

  2. 为什么是正确的?

    二分查找算法之所以是正确的,是因为它利用了有序数组的性质,并通过不断缩小搜索范围的方式来快速定位目标元素。它的基本思想是将待搜索的数组分为两部分,然后通过比较目标值与中间元素的大小关系,确定目标值可能存在的区间,然后在该区间内继续二分查找,直到找到目标值或确定目标值不存在。

    在每一次迭代中,二分查找算法将搜索区间缩小一半,因此它具有高效的搜索速度。由于每次都是将搜索区间减半,所以它的时间复杂度是O(log n),其中n是数组的长度。相比于线性搜索算法的时间复杂度O(n),二分查找算法在大规模数据集上具有更快的速度。

  3. 为什么时间快?

    首先,二分查找算法每次将搜索区间缩小一半。假设待搜索的数组长度为n,在每次迭代中,查找区间的长度都会减半,因此经过k次迭代后,查找区间的长度将变为n/2^k。当查找区间的长度缩小到1时,就可以确定目标值的位置。所以,通过不断将搜索区间减半,二分查找算法能够在较少的比较操作中找到目标值,从而具有较快的时间复杂度。

    其次,二分查找算法是基于有序数组进行查找。由于有序数组具有元素按照大小顺序排列的特点,可以利用这个特点进行二分查找。每次比较目标值与中间元素的大小关系,可以确定目标值在左半部分或右半部分,从而缩小搜索范围。这种有序性质使得二分查找算法能够更快地定位目标值,避免了无效的搜索。

class Solution {
public:int search(vector<int>& nums, int target) {// 初始化左、右双指针int left = 0, right = nums.size() - 1;while(left <= right){int mid = left + (right - left) / 2;if(nums[mid] == target) return mid;else if(nums[mid] < target) left = mid + 1;else right = mid - 1;}return -1;}
};

朴素二分模板

while(left <= right){// 防止漏出int mid = left + (right - left) / 2;if(....) right = mid - 1;else if(....) left = mid + 1;else return ......;}

相关文章:

【二分查找】朴素二分查找

二分查找 题目描述 给定一个 n 个元素有序的&#xff08;升序&#xff09;整型数组 nums 和一个目标值 target &#xff0c;写一个函数搜索 nums 中的 target&#xff0c;如果目标值存在返回下标&#xff0c;否则返回 -1。 示例 1: 输入: nums [-1,0,3,5,9,12], target 9…...

Windows Docker 部署 Redis

部署 Redis 打开 Docker Desktop&#xff0c;切换到 Linux 内核。然后在 PowerShell 执行下面命令&#xff0c;即可启动一个 redis 服务。这里安装的是 7.2.4 版本&#xff0c;如果需要安装其他或者最新版本&#xff0c;可以到 Docker Hub 中进行查找。 docker run -d --nam…...

什么是VR虚拟现实|虚拟科技博物馆|VR设备购买

虚拟现实&#xff08;Virtual Reality&#xff0c;简称VR&#xff09;是一种通过计算机技术模拟出的一种全新的人机交互方式。它可以通过专门的设备&#xff08;如头戴式显示器&#xff09;将用户带入一个计算机生成的虚拟环境之中&#xff0c;使用户能够与这个虚拟环境进行交互…...

高性能API云原生网关 APISIX安装与配置指南

Apache APISIX是Apache软件基金会下的顶级项目&#xff0c;由API7.ai开发并捐赠。它是一个高性能的云原生API网关&#xff0c;具有动态、实时等特点。 APISIX网关可作为所有业务的流量入口&#xff0c;为用户提供了丰富的功能&#xff0c;包括动态路由、动态上游、动态证书、A…...

Gradio Dataframe 学习笔记

Gradio Dataframe 学习笔记 0. 简介1. 使用场景2. 测试数据3. 学习代码4. 更多功能5. 学习资源6. 总结 0. 简介 Gradio是一个用于构建交互式机器学习界面的Python库。它可以轻松创建各种类型的界面&#xff0c;包括用于数据可视化和探索的界面。 Gradio Dataframe 组件是 Gra…...

深入理解计算机系统笔记

1.1 嵌套的数组 当我们创建数组的数组时&#xff0c;数组分配和引用的一般原则也是成立的。 例如&#xff0c;声明 int A[5][3]; 等价于下面的声明 typedef int row3_t[3]; row3_t A[5] 要访问多维数组的元素&#xff0c;编译器会以数组起始为基地址&#xff0c; (可能需…...

300分钟吃透分布式缓存(拉钩教育总结)

开篇寄语 开篇寄语&#xff1a;缓存&#xff0c;你真的用对了吗&#xff1f; 你好&#xff0c;我是你的缓存老师陈波&#xff0c;可能大家对我的网名 fishermen 会更熟悉。 我是资深老码农一枚&#xff0c;经历了新浪微博从起步到当前月活数亿用户的大型互联网系统的技术演进…...

2024亚马逊全球开店注册前需要准备什么?

在2023年出海四小龙SHEIN、Temu、速卖通AliExpress、TikTok Shop快速增长扩张&#xff0c;成为了中国跨境卖家“逃离亚马逊”的新选择。但是&#xff0c;跨境电商看亚马逊。当前&#xff0c;亚马逊仍然是跨境电商行业的绝对老大&#xff0c;占有将近70%成以上的业务份额。 作为…...

android Service 与 activity 通信 并不断传数据

注&#xff1a;这只是个Demo 以下载为案例&#xff0c;实现开启下载&#xff0c;暂停下载&#xff0c;下载进度不断发送给activity class DownloadService : Service() {override fun onBind(intent: Intent?): IBinder? {return MyBinder()}inner class MyBinder : Binder…...

Acwing-基础算法课笔记之数学知识(扩展欧几里得算法)

Acwing-基础算法课笔记之数学知识&#xff08;扩展欧几里得算法&#xff09; 一、扩展欧几里得算法1、裴蜀定理2、过程模拟3、代码模板 二、线性同余方程1、定义2、模拟过程3、结论证明 一、扩展欧几里得算法 1、裴蜀定理 对于任意正整数 a a a&#xff0c; b b b&#xff0…...

简单排列组合题(python版)

文章预览&#xff1a; 题目解法一输出结果 解法二输出结果输出结果 题目 有四个数字:1,2,3,4能组成多少个互不相同且无重复的数字的三位数? 各式多少? 解法一 我们粗略看一下这个题既然我们要组成三位数&#xff0c;那我们就循环3层每一层出一个数&#xff0c;并且if语句判…...

【排坑】搭建 Karmada 环境

git clone 报错 问题&#xff1a;Failed to connect to github.com port 443:connection timed out 解决&#xff1a; git config --global --unset http.proxy【hack/local-up-karmada.sh】 1. karmada ca-certificates (no such package) 问题&#xff1a;fetching http…...

每日一类:Qt GUI开发的基石《QWidget》

深入探索QWidget&#xff1a;Qt GUI开发的基石 在Qt框架中&#xff0c;QWidget类扮演着构建图形用户界面&#xff08;GUI&#xff09;的基础角色。它不仅提供了窗口的基本功能&#xff0c;还允许开发者通过继承和定制来创建各式各样的用户界面元素。本文将详细介绍QWidget的关…...

人大金仓与mysql的差异与替换

人大金仓中不能使用~下面的符号&#xff0c;字段中使用”&#xff0c;无法识别建表语句 创建表时语句中只定义字段名.字段类型.是否是否为空 Varchar类型改为varchar&#xff08;长度 char&#xff09; Int(0) 类型为int4 定义主键&#xff1a;CONSTRAINT 键名 主键类型&#x…...

Excel2LaTeX插件的使用、LaTeX表格

目录 一、下载Excel2Latex 二、使用Excel2Latex 1、将Excel2LaTeX文件添加到加载项 2、导出LaTex的表格数据 3、注意事项 1&#xff09;生成的latex表格断断续续问题 2&#xff09;改变线形的粗细 3&#xff09;表格太大&#xff0c;需要缩小到适应大小 4&#xff09;…...

MySQL 用了哪种默认隔离级别,实现原理是什么?

MySQL 的默认隔离级别是 RR - 可重复读&#xff0c;可以通过命令来查看 MySQL 中的默认隔离级别。 RR - 可重复读是基于多版本并发控制&#xff08;Multi-Version Concurrency Control&#xff0c;MVCC &#xff09;实现的。MVCC&#xff0c;在读取数据时通过一种类似快照的方…...

【C++初阶】第四站:类和对象(下)(理解+详解)

前言&#xff1a; 本篇知识点&#xff1a;初始化列表、explicit关键字、static成员、友元、内部类、匿名对象、编译器的优化 专栏&#xff1a;C初阶 目录 再谈构造函数 1️⃣构造函数体赋值 2️⃣初始化列表 explicit关键字 static成员 1.static概念 2.static特性 面试…...

redis的基本数据类型(一)

redis的基本数据类型 1、redis1.1、数据库分类1.2、NoSQL分类1.3、redis简介1.4、redis应用1.5、如何学习redis 2、redis的安装2.1、Windows安装2.2.1、客户端redis管理工具 2.2、Linux安装&#x1f525;2.2.1、redis核心文件2.2.2、启动方式2.2.3、redis桌面客户端1、redis命令…...

Windows无法识别exFAT格式怎么办?

Windows通常无法读取Mac格式的驱动器。如果使用Apple的HFS Plus将驱动器格式化为exFAT&#xff0c;默认情况下Windows无法读取exFAT驱动器&#xff0c;即使exFAT文件系统与Mac和Windows兼容。事实上&#xff0c;一些制造商销售的“Mac驱动器”是用这种限于Mac的文件系统预先格式…...

AI大模型的发展趋势?

大模型的发展趋势主要体现在以下几个方面&#xff1a; 1、模型规模的增长&#xff1a; 随着数据量和计算能力的不断增加&#xff0c;大型模型的规模也在不断扩大。模型参数数量、层数等指标不断刷新&#xff0c;以应对更复杂的任务和更大规模的数据。 2、多模态融合&#xff…...

Xshell远程连接Kali(默认 | 私钥)Note版

前言:xshell远程连接&#xff0c;私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

家政维修平台实战20:权限设计

目录 1 获取工人信息2 搭建工人入口3 权限判断总结 目前我们已经搭建好了基础的用户体系&#xff0c;主要是分成几个表&#xff0c;用户表我们是记录用户的基础信息&#xff0c;包括手机、昵称、头像。而工人和员工各有各的表。那么就有一个问题&#xff0c;不同的角色&#xf…...

论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(一)

宇树机器人多姿态起立控制强化学习框架论文解析 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架&#xff08;一&#xff09; 论文解读&#xff1a;交大&港大&上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

涂鸦T5AI手搓语音、emoji、otto机器人从入门到实战

“&#x1f916;手搓TuyaAI语音指令 &#x1f60d;秒变表情包大师&#xff0c;让萌系Otto机器人&#x1f525;玩出智能新花样&#xff01;开整&#xff01;” &#x1f916; Otto机器人 → 直接点明主体 手搓TuyaAI语音 → 强调 自主编程/自定义 语音控制&#xff08;TuyaAI…...

多模态图像修复系统:基于深度学习的图片修复实现

多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...

R 语言科研绘图第 55 期 --- 网络图-聚类

在发表科研论文的过程中&#xff0c;科研绘图是必不可少的&#xff0c;一张好看的图形会是文章很大的加分项。 为了便于使用&#xff0c;本系列文章介绍的所有绘图都已收录到了 sciRplot 项目中&#xff0c;获取方式&#xff1a; R 语言科研绘图模板 --- sciRplothttps://mp.…...

基于PHP的连锁酒店管理系统

有需要请加文章底部Q哦 可远程调试 基于PHP的连锁酒店管理系统 一 介绍 连锁酒店管理系统基于原生PHP开发&#xff0c;数据库mysql&#xff0c;前端bootstrap。系统角色分为用户和管理员。 技术栈 phpmysqlbootstrapphpstudyvscode 二 功能 用户 1 注册/登录/注销 2 个人中…...

wpf在image控件上快速显示内存图像

wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像&#xff08;比如分辨率3000*3000的图像&#xff09;的办法&#xff0c;尤其是想把内存中的裸数据&#xff08;只有图像的数据&#xff0c;不包…...