算法 —— 二分查找
目录
二分查找
在排序数组中查找元素的第一个和最后一个位置
搜索插入位置
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的平方根 山峰数组的峰顶索引 寻找峰值 搜索旋转排序数组中的最⼩值 点名 二分查找模板分为三种:1、朴素的二分模板 2、查找左边界的二分模板 3、查找右边界的二分模板…...
Mysql explain语句详解与实例展示
首先简单介绍sql: SQL语言共分为四大类:数据查询语言DQL,数据操纵语言DML,数据定义语言DDL,数据控制语言DCL。 1. 数据查询语言DQL 数据查询语言DQL基本结构是由SELECT子句,FROM子句,WHERE子句…...
Python基础问题汇总
为什么学习Python? 易学易用:Python语法简洁清晰,易于学习。广泛的应用领域:适用于Web开发、数据科学、人工智能、自动化脚本等多种场景。强大的库支持:拥有丰富的第三方库,如NumPy、Pandas、TensorFlow等…...
【讲解下iOS语言基础】
🌈个人主页: 程序员不想敲代码啊 🏆CSDN优质创作者,CSDN实力新星,CSDN博客专家 👍点赞⭐评论⭐收藏 🤝希望本文对您有所裨益,如有不足之处,欢迎在评论区提出指正,让我们共…...
【网络安全】实验一(网络拓扑环境的搭建)
一、本次实验的实验目的 学习利用 VMware 创建虚拟环境 学习利用 VMware 搭建各自网络拓扑环境 二、创建虚拟机 三、克隆虚拟机 选择克隆的系统必须处于关机状态。 方法一: 方法二: 需要修改克隆计算机的名字,避免产生冲突。 四、按照要求完…...
Docker-基础
一,Docker简介,功能特性与应用场景 1.1 Docker简介 Docker是一个开源的应用容器引擎,让开发者可以打包他们的应用以及依赖包到一个可移植的容器中,然后发布到任何流行的Linux机器上,也可以实现虚拟化,容器…...
《昇思25天学习打卡营第14天|onereal》
第14天学习内容如下: Diffusion扩散模型 本文基于Hugging Face:The Annotated Diffusion Model一文翻译迁移而来,同时参考了由浅入深了解Diffusion Model一文。 本教程在Jupyter Notebook上成功运行。如您下载本文档为Python文件,…...
LeetCode 744, 49, 207
目录 744. 寻找比目标字母大的最小字母题目链接标签思路代码 49. 字母异位词分组题目链接标签思路代码 207. 课程表题目链接标签思路代码 744. 寻找比目标字母大的最小字母 题目链接 744. 寻找比目标字母大的最小字母 标签 数组 二分查找 思路 本题比 基础二分查找 难的一…...
【AI资讯】可以媲美GPT-SoVITS的低显存开源文本转语音模型Fish Speech
Fish Speech是一款由fishaudio开发的全新文本转语音工具,支持中英日三种语言,语音处理接近人类水平,使用Flash-Attn算法处理大规模数据,提供高效、准确、稳定的TTS体验。 Fish Audio...
微服务数据流的协同:Eureka与Spring Cloud Data Flow集成指南
微服务数据流的协同:Eureka与Spring Cloud Data Flow集成指南 在构建基于Spring Cloud的微服务架构时,服务发现和数据流处理是两个关键的组成部分。Eureka作为服务发现工具,而Spring Cloud Data Flow提供了数据流处理的能力。本文将详细介绍…...
java生成json格式文件(包含缩进等格式)
生成json文件的同时保留原json格式,拥有良好的格式(如缩进等),提供友善阅读支持。 pom.xml依赖增加: <dependency><groupId>com.google.code.gson</groupId><artifactId>gson</artifactI…...
Python面试题:如何在 Python 中读取和写入 JSON 文件?
在 Python 中读取和写入 JSON 文件可以使用 json 模块。以下是具体的示例,展示了如何读取和写入 JSON 文件。 读取 JSON 文件 要读取 JSON 文件,可以使用 json.load() 方法。下面是一个示例代码: import json# 假设有一个名为 data.json 的…...
FlutterWeb渲染模式及提速
背景 在使用Flutter Web开发的网站过程中,常常会遇到不同浏览器之间的兼容性问题。例如,在Google浏览器中动画和交互都非常流畅,但在360浏览器中却会出现卡顿现象;在Google浏览器中动态设置图标颜色正常显示,而在Safa…...
群体优化算法----化学反应优化算法介绍,解决蛋白质-配体对接问题示例
介绍 化学反应优化算法(Chemical Reaction Optimization, CRO)是一种新兴的基于自然现象的元启发式算法,受化学反应过程中分子碰撞和反应机制的启发而设计。CRO算法模拟了分子在化学反应过程中通过能量转换和分子间相互作用来寻找稳定结构的…...
Go语言如何入门,有哪些书推荐?
Go 语言之所以如此受欢迎,其编译器功不可没。Go 语言的发展也得益于其编译速度够快。 对开发者来说,更快的编译速度意味着更短的反馈周期。大型的 Go 应用程序总是能在几秒钟之 内完成编译。而当使用 go run编译和执行小型的 Go 应用程序时,其…...
【密码学】密码学体系
密码学体系是信息安全领域的基石,它主要分为两大类:对称密码体制和非对称密码体制。 一、对称密码体制(Symmetric Cryptography) 在对称密码体制中,加密和解密使用相同的密钥。这意味着发送方和接收方都必须事先拥有这…...
Bean的管理
1.主动获取Bean spring项目在需要时,会自动从IOC容器中获取需要的Bean 我们也可以自己主动的得到Bean对象 (1)获取bean对象,首先获取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、进程: 计算机中的程序关于某数据集合上的一次运行活动。 狭义定义:进程是正在运行的程序的实例(an instance of a computer program that is being executed)。广义定义:进程是一个具有一定独立功能的程序关于某个…...
某某市信息科技学业水平测试软件打开加载失败逆向分析(笔记)
引言:笔者在工作过程中,用户上报某某市信息科技学业水平测试软件在云电脑上打开初始化的情况下出现了加载和绑定机器失败的问题。一般情况下,在实体机上用户进行登录后,用户的账号信息跟主机的机器码进行绑定然后保存到配置文件&a…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
超短脉冲激光自聚焦效应
前言与目录 强激光引起自聚焦效应机理 超短脉冲激光在脆性材料内部加工时引起的自聚焦效应,这是一种非线性光学现象,主要涉及光学克尔效应和材料的非线性光学特性。 自聚焦效应可以产生局部的强光场,对材料产生非线性响应,可能…...
React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...
ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...
React Native在HarmonyOS 5.0阅读类应用开发中的实践
一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强,React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 (1)使用React Native…...
oracle与MySQL数据库之间数据同步的技术要点
Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异,它们的数据同步要求既要保持数据的准确性和一致性,又要处理好性能问题。以下是一些主要的技术要点: 数据结构差异 数据类型差异ÿ…...
tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...
RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
return this;返回的是谁
一个审批系统的示例来演示责任链模式的实现。假设公司需要处理不同金额的采购申请,不同级别的经理有不同的审批权限: // 抽象处理者:审批者 abstract class Approver {protected Approver successor; // 下一个处理者// 设置下一个处理者pub…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
