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

算法 —— 二分查找

目录

二分查找

在排序数组中查找元素的第一个和最后一个位置

搜索插入位置

x的平方根

山峰数组的峰顶索引

寻找峰值

搜索旋转排序数组中的最⼩值

点名


 二分查找模板分为三种:1、朴素的二分模板   2、查找左边界的二分模板  3、查找右边界的二分模板(注意:不是数组有序才使用二分查找,只要存在二段性(一个条件把数组分为两段)都可以使用二分查找)


二分查找

 代码如下:

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)right = mid - 1;else if (nums[mid] < target)left = mid + 1;elsereturn mid;}return -1;}
};

在排序数组中查找元素的第一个和最后一个位置

这道题可以引出另外两个重要的二分查找模板: 查找左边界的二分模板   查找右边界的二分模板

 以上是两个模板的内容,判断条件根据题目内容修改,以题目示例1为例,下面给出具体解释为什么这样做可行:

 代码如下:

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {// 处理为空if (nums.size() == 0)return { -1,-1 };// 找左端点int left_end_point = -1, right_end_point = -1;int left = 0, right = nums.size() - 1;while (left < right){int mid = left + (right - left) / 2;if (nums[mid] < target)left = mid + 1;elseright = mid;}// 判断是否有结果if(nums[left]==target)left_end_point = left;// 找右端点   // left可以从左端点开始left = 0, right = nums.size() - 1;while (left < right){int mid = left + (right - left + 1) / 2;if (nums[mid] > target)right = mid - 1;elseleft = mid;}if(nums[right] == target)right_end_point = right;if(right_end_point != -1)return { left_end_point,right_end_point };elsereturn { -1,-1 };}
};

搜索插入位置

根据 二段性,可以把数组分为小于t和大于等于t两部分,目标索引就是在大于等于的左边界上。

注意示例3的边界情况,代码如下:

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0, right = nums.size();while (left < right){int mid = left + (right - left) / 2;if (nums[mid] < target)left = mid + 1;elseright = mid;}// 数组中所有元素小于targetif (nums[left] < target)return left + 1;return right;}
};

x的平方根

本题依旧是一个二分查找的算法思想,left为1,right为x本身,根据二段性,将x分为小于等于sqrt(x)的和大于sqrt(x)的注意小于1的小数和INT_MAX这两个特殊情况, INT_MAX平方后数据太大,要用long long类型来存储。代码如下:

class Solution {
public:int mySqrt(int x) {// 处理边界情况if (x < 1)return 0;int left = 1, right = x;while (left < right){long long mid = left + (right - left + 1) / 2; // 防止溢出if (mid * mid > x)right = mid - 1;elseleft = mid;}return left;}
};

山峰数组的峰顶索引

本题依旧是一道二分查找题,数组被分为递增段和递减端两部分,代码如下:

class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {int left = 1, right = arr.size() - 2;while (left < right){int mid = left + (right - left + 1) / 2;if (arr[mid] < arr[mid - 1])right = mid - 1;elseleft = mid;}return left;}
};

寻找峰值

class Solution {
public:int findPeakElement(vector<int>& nums) {int left = 0, right = nums.size() - 1;while (left < right){int mid = left + (right - left) / 2;if (nums[mid] < nums[mid + 1])left = mid + 1;elseright = mid;}return left;}
};

搜索旋转排序数组中的最⼩值

class Solution {
public:int findMin(vector<int>& nums) {int left = 0, right = nums.size() - 1, target = nums[right];while (left < right){int mid = left + (right - left) / 2;if (nums[mid] > target)left = mid + 1;elseright = mid;}return nums[right];}
};

点名

 本题可以有多种解法:

此题查找的是左边界,直接写代码即可:

class Solution {
public:int takeAttendance(vector<int>& records) {int left = 0, right = records.size() - 1;while (left < right){int mid = left + (right - left) / 2;if (records[mid] == mid)left = mid + 1;elseright = mid;}// 特殊情况0 1 2 3 缺少4return records[left] == left ? left + 1 : left;}
};

相关文章:

算法 —— 二分查找

目录 二分查找 在排序数组中查找元素的第一个和最后一个位置 搜索插入位置 x的平方根 山峰数组的峰顶索引 寻找峰值 搜索旋转排序数组中的最⼩值 点名 二分查找模板分为三种&#xff1a;1、朴素的二分模板 2、查找左边界的二分模板 3、查找右边界的二分模板&#xf…...

Mysql explain语句详解与实例展示

首先简单介绍sql&#xff1a; SQL语言共分为四大类&#xff1a;数据查询语言DQL&#xff0c;数据操纵语言DML&#xff0c;数据定义语言DDL&#xff0c;数据控制语言DCL。 1. 数据查询语言DQL 数据查询语言DQL基本结构是由SELECT子句&#xff0c;FROM子句&#xff0c;WHERE子句…...

Python基础问题汇总

为什么学习Python&#xff1f; 易学易用&#xff1a;Python语法简洁清晰&#xff0c;易于学习。广泛的应用领域&#xff1a;适用于Web开发、数据科学、人工智能、自动化脚本等多种场景。强大的库支持&#xff1a;拥有丰富的第三方库&#xff0c;如NumPy、Pandas、TensorFlow等…...

【讲解下iOS语言基础】

&#x1f308;个人主页: 程序员不想敲代码啊 &#x1f3c6;CSDN优质创作者&#xff0c;CSDN实力新星&#xff0c;CSDN博客专家 &#x1f44d;点赞⭐评论⭐收藏 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共…...

【网络安全】实验一(网络拓扑环境的搭建)

一、本次实验的实验目的 学习利用 VMware 创建虚拟环境 学习利用 VMware 搭建各自网络拓扑环境 二、创建虚拟机 三、克隆虚拟机 选择克隆的系统必须处于关机状态。 方法一&#xff1a; 方法二&#xff1a; 需要修改克隆计算机的名字&#xff0c;避免产生冲突。 四、按照要求完…...

Docker-基础

一&#xff0c;Docker简介&#xff0c;功能特性与应用场景 1.1 Docker简介 Docker是一个开源的应用容器引擎&#xff0c;让开发者可以打包他们的应用以及依赖包到一个可移植的容器中&#xff0c;然后发布到任何流行的Linux机器上&#xff0c;也可以实现虚拟化&#xff0c;容器…...

《昇思25天学习打卡营第14天|onereal》

第14天学习内容如下&#xff1a; Diffusion扩散模型 本文基于Hugging Face&#xff1a;The Annotated Diffusion Model一文翻译迁移而来&#xff0c;同时参考了由浅入深了解Diffusion Model一文。 本教程在Jupyter Notebook上成功运行。如您下载本文档为Python文件&#xff0c…...

LeetCode 744, 49, 207

目录 744. 寻找比目标字母大的最小字母题目链接标签思路代码 49. 字母异位词分组题目链接标签思路代码 207. 课程表题目链接标签思路代码 744. 寻找比目标字母大的最小字母 题目链接 744. 寻找比目标字母大的最小字母 标签 数组 二分查找 思路 本题比 基础二分查找 难的一…...

【AI资讯】可以媲美GPT-SoVITS的低显存开源文本转语音模型Fish Speech

Fish Speech是一款由fishaudio开发的全新文本转语音工具&#xff0c;支持中英日三种语言&#xff0c;语音处理接近人类水平&#xff0c;使用Flash-Attn算法处理大规模数据&#xff0c;提供高效、准确、稳定的TTS体验。 Fish Audio...

微服务数据流的协同:Eureka与Spring Cloud Data Flow集成指南

微服务数据流的协同&#xff1a;Eureka与Spring Cloud Data Flow集成指南 在构建基于Spring Cloud的微服务架构时&#xff0c;服务发现和数据流处理是两个关键的组成部分。Eureka作为服务发现工具&#xff0c;而Spring Cloud Data Flow提供了数据流处理的能力。本文将详细介绍…...

java生成json格式文件(包含缩进等格式)

生成json文件的同时保留原json格式&#xff0c;拥有良好的格式&#xff08;如缩进等&#xff09;&#xff0c;提供友善阅读支持。 pom.xml依赖增加&#xff1a; <dependency><groupId>com.google.code.gson</groupId><artifactId>gson</artifactI…...

Python面试题:如何在 Python 中读取和写入 JSON 文件?

在 Python 中读取和写入 JSON 文件可以使用 json 模块。以下是具体的示例&#xff0c;展示了如何读取和写入 JSON 文件。 读取 JSON 文件 要读取 JSON 文件&#xff0c;可以使用 json.load() 方法。下面是一个示例代码&#xff1a; import json# 假设有一个名为 data.json 的…...

FlutterWeb渲染模式及提速

背景 在使用Flutter Web开发的网站过程中&#xff0c;常常会遇到不同浏览器之间的兼容性问题。例如&#xff0c;在Google浏览器中动画和交互都非常流畅&#xff0c;但在360浏览器中却会出现卡顿现象&#xff1b;在Google浏览器中动态设置图标颜色正常显示&#xff0c;而在Safa…...

群体优化算法----化学反应优化算法介绍,解决蛋白质-配体对接问题示例

介绍 化学反应优化算法&#xff08;Chemical Reaction Optimization, CRO&#xff09;是一种新兴的基于自然现象的元启发式算法&#xff0c;受化学反应过程中分子碰撞和反应机制的启发而设计。CRO算法模拟了分子在化学反应过程中通过能量转换和分子间相互作用来寻找稳定结构的…...

Go语言如何入门,有哪些书推荐?

Go 语言之所以如此受欢迎&#xff0c;其编译器功不可没。Go 语言的发展也得益于其编译速度够快。 对开发者来说&#xff0c;更快的编译速度意味着更短的反馈周期。大型的 Go 应用程序总是能在几秒钟之 内完成编译。而当使用 go run编译和执行小型的 Go 应用程序时&#xff0c;其…...

【密码学】密码学体系

密码学体系是信息安全领域的基石&#xff0c;它主要分为两大类&#xff1a;对称密码体制和非对称密码体制。 一、对称密码体制&#xff08;Symmetric Cryptography&#xff09; 在对称密码体制中&#xff0c;加密和解密使用相同的密钥。这意味着发送方和接收方都必须事先拥有这…...

Bean的管理

1.主动获取Bean spring项目在需要时&#xff0c;会自动从IOC容器中获取需要的Bean 我们也可以自己主动的得到Bean对象 &#xff08;1&#xff09;获取bean对象&#xff0c;首先获取SpringIOC对象 private ApplicationContext applicationContext //IOC容器对象 (2 )方法…...

Unity 数据持久化【PlayerPrefs】

1、数据持久化 文章目录 1、数据持久化PlayerPrefs基本方法1、PlayerPrefs概念2、存储相关3、读取相关4、删除数据思考 信息的存储和读取 PlayerPrefs存储位置1、PlayerPrefs存储的数据在哪个位置2、PlayerPrefs 数据唯一性思考 排行榜功能 2、Playerprefs实践1、必备知识点-反…...

linux-虚拟内存-虚拟cpu

1、进程&#xff1a; 计算机中的程序关于某数据集合上的一次运行活动。 狭义定义&#xff1a;进程是正在运行的程序的实例&#xff08;an instance of a computer program that is being executed&#xff09;。广义定义&#xff1a;进程是一个具有一定独立功能的程序关于某个…...

某某市信息科技学业水平测试软件打开加载失败逆向分析(笔记)

引言&#xff1a;笔者在工作过程中&#xff0c;用户上报某某市信息科技学业水平测试软件在云电脑上打开初始化的情况下出现了加载和绑定机器失败的问题。一般情况下&#xff0c;在实体机上用户进行登录后&#xff0c;用户的账号信息跟主机的机器码进行绑定然后保存到配置文件&a…...

后进先出(LIFO)详解

LIFO 是 Last In, First Out 的缩写&#xff0c;中文译为后进先出。这是一种数据结构的工作原则&#xff0c;类似于一摞盘子或一叠书本&#xff1a; 最后放进去的元素最先出来 -想象往筒状容器里放盘子&#xff1a; &#xff08;1&#xff09;你放进的最后一个盘子&#xff08…...

手游刚开服就被攻击怎么办?如何防御DDoS?

开服初期是手游最脆弱的阶段&#xff0c;极易成为DDoS攻击的目标。一旦遭遇攻击&#xff0c;可能导致服务器瘫痪、玩家流失&#xff0c;甚至造成巨大经济损失。本文为开发者提供一套简洁有效的应急与防御方案&#xff0c;帮助快速应对并构建长期防护体系。 一、遭遇攻击的紧急应…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

热门Chrome扩展程序存在明文传输风险,用户隐私安全受威胁

赛门铁克威胁猎手团队最新报告披露&#xff0c;数款拥有数百万活跃用户的Chrome扩展程序正在通过未加密的HTTP连接静默泄露用户敏感数据&#xff0c;严重威胁用户隐私安全。 知名扩展程序存在明文传输风险 尽管宣称提供安全浏览、数据分析或便捷界面等功能&#xff0c;但SEMR…...

倒装芯片凸点成型工艺

UBM&#xff08;Under Bump Metallization&#xff09;与Bump&#xff08;焊球&#xff09;形成工艺流程。我们可以将整张流程图分为三大阶段来理解&#xff1a; &#x1f527; 一、UBM&#xff08;Under Bump Metallization&#xff09;工艺流程&#xff08;黄色区域&#xff…...

【java面试】微服务篇

【java面试】微服务篇 一、总体框架二、Springcloud&#xff08;一&#xff09;Springcloud五大组件&#xff08;二&#xff09;服务注册和发现1、Eureka2、Nacos &#xff08;三&#xff09;负载均衡1、Ribbon负载均衡流程2、Ribbon负载均衡策略3、自定义负载均衡策略4、总结 …...