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

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

深入浅出:JavaScript 中的 `window.crypto.getRandomValues()` 方法

深入浅出&#xff1a;JavaScript 中的 window.crypto.getRandomValues() 方法 在现代 Web 开发中&#xff0c;随机数的生成看似简单&#xff0c;却隐藏着许多玄机。无论是生成密码、加密密钥&#xff0c;还是创建安全令牌&#xff0c;随机数的质量直接关系到系统的安全性。Jav…...

解锁数据库简洁之道:FastAPI与SQLModel实战指南

在构建现代Web应用程序时&#xff0c;与数据库的交互无疑是核心环节。虽然传统的数据库操作方式&#xff08;如直接编写SQL语句与psycopg2交互&#xff09;赋予了我们精细的控制权&#xff0c;但在面对日益复杂的业务逻辑和快速迭代的需求时&#xff0c;这种方式的开发效率和可…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

佰力博科技与您探讨热释电测量的几种方法

热释电的测量主要涉及热释电系数的测定&#xff0c;这是表征热释电材料性能的重要参数。热释电系数的测量方法主要包括静态法、动态法和积分电荷法。其中&#xff0c;积分电荷法最为常用&#xff0c;其原理是通过测量在电容器上积累的热释电电荷&#xff0c;从而确定热释电系数…...

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...