C++ 二分法

目录

1、704. 二分查找 

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

3、69. x的平方根

4、35. 搜索插入位置

5、852. 山脉数组的峰顶索引 

6、162. 寻找峰值

7、153. 寻找旋转排序数组中的最小值 

8、LCR 173. 点名 

1、704. 二分查找 

​

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

思路：

首先，定义了两个变量left和right，分别表示数组的左边界和右边界。初始时，left被设置为数组的第一个元素的索引（0），right被设置为数组的最后一个元素的索引（nums.size() - 1）。

然后，使用一个循环来执行二分查找。循环条件是left小于等于right，这表示还存在未查找的区间。在二分查找算法中，使用left <= right作为循环条件是为了处理以下两种情况：

  1. 当查找区间只剩下一个元素时，即left和right指向同一个位置时，仍然需要进行一次比较。如果使用left < right作为循环条件，那么在这种情况下循环会提前结束，导致无法正确判断目标值是否存在。

  2. 当查找区间为空时，即left大于right时，循环条件为假，可以直接退出循环。这种情况下，表示目标值不存在于数组中。

在每次循环中，首先计算中间元素的索引mid，通过将左边界和右边界与左边界之差相加除以2得到。这样可以将查找区间缩小一半，并且不会超出整形范围。

接下来，通过比较中间元素nums[mid]和目标值target的大小关系，来确定下一步的查找方向。

  • 如果nums[mid]小于target，说明目标值在右半部分，将left更新为mid + 1，缩小查找区间为右半部分。
  • 如果nums[mid]大于target，说明目标值在左半部分，将right更新为mid - 1，缩小查找区间为左半部分。
  • 如果nums[mid]等于target，说明找到了目标值，直接返回mid作为结果。

如果循环结束时仍然没有找到目标值，即left大于right，则返回-1表示未找到。

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

​

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {if (nums.size() == 0)return {-1, -1};int left = 0, right = nums.size() - 1;int begin = 0;// 使用二分查找找到目标值的最左边界while (left < right) {int mid = left + (right - left) / 2;if (nums[mid] < target)left = mid + 1;elseright = mid;}// 检查最左边界的元素是否为目标值if (nums[left] != target)return {-1, -1};elsebegin = left;left = 0, right = nums.size() - 1;// 使用二分查找找到目标值的最右边界while (left < right) {int mid = left + (right - left + 1) / 2;if (nums[mid] <= target)left = mid;elseright = mid - 1;}return {begin, right};}
};

思路：寻找左右边界

首先，检查数组是否为空，如果为空，则直接返回{-1, -1}表示未找到目标值。

初始化左边界left为0，右边界right为数组长度减1。

使用二分查找来找到目标值的最左边界。循环条件是left < right。

  1. 在每次循环中，计算中间元素的索引mid。
  2. 比较中间元素nums[mid]与目标值target的大小关系：
    1. 如果nums[mid]小于目标值，说明目标值在右半部分，将left更新为mid + 1，缩小查找区间为右半部分。
    2. 如果nums[mid]大于等于目标值，说明目标值在左半部分，将right更新为mid，缩小查找区间为左半部分。
  3. 检查最左边界的元素是否为目标值。如果不是目标值，则表示未找到目标值，直接返回{-1, -1}。

将最左边界left赋值给begin，作为目标值的起始位置。

重新初始化left和right，继续使用二分查找来找到目标值的最右边界。循环条件是left < right。

  1. 在每次循环中，计算中间元素的索引mid，。
  2. 比较中间元素nums[mid]与目标值target的大小关系：
    1. 如果nums[mid]小于等于目标值，将left更新为mid，缩小查找区间为右半部分。
    2. 如果nums[mid]大于目标值，将right更新为mid - 1，缩小查找区间为左半部分。
  3. 返回结果为{begin, right}，其中begin为目标值的最左边界，right为目标值的最右边界。

​

3、69. x的平方根

​ 

思路：寻找左右边界 

首先，检查输入的数x是否小于1，如果是，则直接返回0。

然后，定义了两个变量left和right，分别表示查找区间的左边界和右边界。初始时，left被设置为1，right被设置为x。

接下来，使用二分查找来逼近平方根的值。循环条件是left < right，这表示还存在未查找的区间。

在每次循环中，首先计算中间元素的值mid，通过将左边界和右边界相加除以2得到。这里使用了(right - left + 1) / 2来确保向上取整，以保证查找区间向上移动。

然后，通过比较中间元素的平方mid * mid与目标值x的大小关系，来确定下一步的查找方向。

  • 如果mid * mid小于等于x，说明平方根在右半部分，将left更新为mid，缩小查找区间为右半部分。
  • 如果mid * mid大于x，说明平方根在左半部分，将right更新为mid - 1，缩小查找区间为左半部分。

最后，循环结束时，left和right相等，表示找到了平方根的整数部分。返回left作为结果。

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)left = mid;elseright = mid - 1;}return left;}
};

​

4、35. 搜索插入位置

​

思路：寻找左边界 

class Solution {
public:int searchInsert(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)left = mid + 1;elseright = mid;}if (nums[left] < target)return right + 1;elsereturn right;}
};

 思路：寻找右边界 

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

​

5、852. 山脉数组的峰顶索引 

思路：寻找左边界  

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

两个解决方案都是有效的，并且都具有 O(log(n)) 的时间复杂度。它们的区别在于二分查找的条件判断。

  • 第一个解决方案中，二分查找的条件判断是 arr[mid] > arr[mid - 1]，即判断当前位置的元素是否大于前一个元素。如果满足这个条件，则说明峰值在当前位置或右侧，将 left 更新为 mid；否则，峰值在左侧，将 right 更新为 mid - 1。
  • 第二个解决方案中，二分查找的条件判断是 arr[mid] < arr[mid + 1]，即判断当前位置的元素是否小于后一个元素。如果满足这个条件，则说明峰值在右侧，将 left 更新为 mid + 1；否则，峰值在左侧或当前位置，将 right 更新为 mid。

6、162. 寻找峰值

 思路：寻找左边界 

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 findPeakElement(vector<int>& nums) {int left = 0, right = nums.size() - 1;while (left < right) {int mid = left + (right - left + 1) / 2;if (nums[mid] > nums[mid - 1])left = mid;elseright = mid - 1;}return left;}
};

7、153. 寻找旋转排序数组中的最小值 

 思路：以最右端点为基准点进行比较，逐渐缩小范围。

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

8、LCR 173. 点名 

思路：根据数组元素与下标相等和不相等划分两个区间，最后，如果元素与其下标不相等，则返回其下标即为所缺元素；如果元素与其下标相等，则所缺元素为数组最大元素加一，即为left或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;}return left == records[left] ? left + 1 : left;}
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://xiahunao.cn/news/2806374.html

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

2024 windows环境下安装RabbitMQ（亲测超详细）

2024 windows环境下安装RabbitMQ（亲测超详细）

一、RabbitMQ是什么&#xff1f;   RabbitMQ 是一个由 Erlang 语言开发的 AMQP 的开源实现。 ​ AMQP &#xff1a;Advanced Message Queue&#xff0c;高级消息队列协议。它是应用层协议的一个开放标准&#xff0c;为面向消息的中间件设计&#xff0c;基于此协议的客户端与消…
阅读更多...
[C++] 如何操作ini文件

[C++] 如何操作ini文件

什么是ini文件&#xff1f; INI文件&#xff08;.ini&#xff09;是一种常见的配置文件格式&#xff0c;用于存储程序、操作系统或设备驱动程序的配置信息。INI是"Initialization"的缩写&#xff0c;指的是初始化。INI文件通常是纯文本文件&#xff0c;在Windows操作…
阅读更多...
【c++】模板初阶（泛型编程与模板）

【c++】模板初阶（泛型编程与模板）

1.泛型编程 如何实现一个通用的交换函数呢&#xff1f; void Swap(int& left, int& right) {int temp left;left right;right temp; } void Swap(double& left, double& right) {double temp left;left right;right temp; } void Swap(char& left, …
阅读更多...
论文精读--GPT1

论文精读--GPT1

把transformer的解码器拿出来&#xff0c;在没有标号的大量文本数据上训练一个语言模型&#xff0c;来获得预训练模型&#xff0c;然后到子任务上微调&#xff0c;得到每个任务所需的分类器 Abstract Natural language understanding comprises a wide range of diverse tasks…
阅读更多...
RabbitMq：什么是RabbitMq？ ①

RabbitMq：什么是RabbitMq？ ①

一、RabbitMq定位 RabbitMq是一个基于消息订阅发布的一款消息中间件。 二、技术原理 核心概念 server&#xff1a;又称broker&#xff0c;接受客户端连接&#xff0c;实现AMQP实体服务。缓存代理&#xff0c;Kafka集群中的一台或多台服务器统称broker.connection&#xff1a;…
阅读更多...
C++初阶：容器适配器priority_queue常用接口详解及模拟实现、仿函数介绍

C++初阶：容器适配器priority_queue常用接口详解及模拟实现、仿函数介绍

介绍完了stack和queue的介绍以及模拟的相关内容后&#xff1a;C初阶&#xff1a;容器适配器介绍、stack和queue常用接口详解及模拟实现 接下来进行priority_queue的介绍以及模拟&#xff1a; 文章目录 1.priority_queue的介绍和使用1.1priority_queue的初步介绍1.2priority_que…
阅读更多...
模型 3C(顾客、公司、竞争)战略

模型 3C(顾客、公司、竞争)战略

系列文章 分享 模型&#xff0c;了解更多&#x1f449; 模型_总纲目录。洞悉自身&#xff0c;把握顾客&#xff0c;超越竞争。 1 3C(顾客、公司、竞争)战略模型的应用 1.1 3C战略模型在麦当劳公司中的应用 麦当劳在扩张国际市场时采用3C战略模型&#xff0c;具体如下&#xf…
阅读更多...
Covalent Network（CQT）发展新里程碑：SOC 2 数据安全认证通过，进一步加强了其人工智能支持

Covalent Network（CQT）发展新里程碑：SOC 2 数据安全认证通过，进一步加强了其人工智能支持

Covalent Network&#xff08;CQT&#xff09;现已完成并通过了严格的 Service Organization Control&#xff08;SOC) 2 Type II 的合规性审计&#xff0c;通过由备受行业认可的机构执行&#xff0c;进一步证明了 Covalent Network&#xff08;CQT&#xff09;团队坚定不移地致…
阅读更多...
什么是nginx 、安装nginx、nginx调优

什么是nginx 、安装nginx、nginx调优

一、 什么是nginx 1.1 nginx的概念 一款高新能、轻量级Web服务软件系统资源消耗低对HTTP并发连接的处理能力高单台物理服务器可支持30 000&#xff5e;50 000个并发请求。 1.2 nginx模块与作用 核心模块&#xff1a;是 Nginx 服务器正常运行必不可少的模块&#xff0c;提供错…
阅读更多...
数字电路 第二章—第一节（门电路—概述）

数字电路 第二章—第一节（门电路—概述）

一、门电路的概念 实现基本和常用逻辑运算的电子电路称为逻辑门电路&#xff0c;简称门电路。例如&#xff0c;实现与运算的称为与门&#xff0c;实现或运算的称为或门&#xff0c;实现非运算的称为非门&#xff0c;也称为反相器&#xff1b;类似地&#xff0c;实现与非、或非、…
阅读更多...
vue+nodejs+uniapp婚纱定制婚庆摄影系统 微信小程序 springboot+python

vue+nodejs+uniapp婚纱定制婚庆摄影系统 微信小程序 springboot+python

目前移动互联网大行其道&#xff0c;人人都手中拿着智能机&#xff0c;手机手机&#xff0c;手不离机&#xff0c;如果开发一个用在手机上的程序软件&#xff0c;那是多么的符合潮流&#xff0c;符合管理者和客户的理想。本次就是开发婚庆摄影小程序&#xff0c;有管理员&#…
阅读更多...
knife4j springboot3使用

knife4j springboot3使用

简介 在日常开发中&#xff0c;写接口文档是我们必不可少的&#xff0c;而Knife4j就是一个接口文档工具&#xff0c;可以看作是Swagger的升级版&#xff0c;但是界面比Swagger更好看&#xff0c;功能更丰富 使用 我使用的是springboot3.2.3 knife4j 4.3.0,knife4j 4.4版本有…
阅读更多...
python[6]

python[6]

类和对象 面向对象编程–说白就是让对象干活 创建类&#xff1a;class 类名&#xff1a; 创建类对象 对象名 类名&#xff08;&#xff09; 构造方法 1、构造方法的名称是__init__ 2、构造方法的作用&#xff1f; 构建类对象的时候会自动运行 构建类对象的传参会传递给构造…
阅读更多...
Linux：Jenkins：GitLab+Maven+Jenkins的部署

Linux：Jenkins：GitLab+Maven+Jenkins的部署

1.环境 我这里准备了三台centos7 1.用于部署gitlab 运行内存&#xff1a;6G 名字&#xff1a;Jenkins-GitLab 192.168.6.1 2.用于部署jenkins 运行内存&#xff1a;2G 名字&#xff1a;Jenkins-server 192.168.6.2 3.用于打包测试…
阅读更多...
GO-ICP的使用(一)

GO-ICP的使用(一)

一、代码下载以、修改以及使用 下载&#xff1a; 链接&#xff1a;yangjiaolong/Go-ICP: Implementation of the Go-ICP algorithm for globally optimal 3D pointset registration (github.com) 解压之后 &#xff1a; 首先visual studio项目&#xff0c;配置好PCL环境&…
阅读更多...
【leetcode热题】不同的子序列

【leetcode热题】不同的子序列

给你两个字符串 s 和 t &#xff0c;统计并返回在 s 的 子序列 中 t 出现的个数&#xff0c;结果需要对 109 7 取模。 示例 1&#xff1a; 输入&#xff1a;s "rabbbit", t "rabbit" 输出&#xff1a;3 解释&#xff1a; 如下所示, 有 3 种可以从 s 中…
阅读更多...
Ps：明度直方图

Ps：明度直方图

明度 Luminosity直方图显示了图像中各个亮度级别的像素分布情况。 与 RGB 直方图不同&#xff0c;“明度”直方图专注于图像的亮度信息&#xff0c;而不是单独的颜色信息。 在“直方图”面板的通道中选择“明度”。 “明度”直方图提供了一种量化的方式来理解图像的整体明暗结构…
阅读更多...
数字滚动实现

数字滚动实现

介绍 vue-countup-v3 插件是一个基于 Vue3 的数字动画插件&#xff0c;用于在网站或应用程序中创建带有数字动画效果的计数器。通过该插件&#xff0c;我们可以轻松地实现数字的递增或递减动画&#xff0c;并自定义其样式和动画效果。该插件可以用于许多场景&#xff0c;例如展…
阅读更多...
MYSQL安装及卸载

MYSQL安装及卸载

目录 一、下载 二、解压 三、配置 1. 添加环境变量 2. 初始化MySQL 3. 注册MySQL服务 4. 启动MySQL服务 5. 修改默认账户密码 四、登录MySQL 五、卸载MySQL 一、下载 点开下面的链接&#xff1a;MySQL :: Download MySQL Community Server 点击Download 就可以下载对…
阅读更多...
【深度学习目标检测】十八、基于深度学习的人脸检测系统-含GUI和源码（python，yolov8）

【深度学习目标检测】十八、基于深度学习的人脸检测系统-含GUI和源码（python，yolov8）

人脸检测是计算机视觉中的一个重要方向&#xff0c;也是一个和人们生活息息相关的研究方向&#xff0c;因为人脸是人最重要的外貌特征。人脸检测技术的重要性主要体现在以下几个方面&#xff1a; 人脸识别与安全&#xff1a;人脸检测是人脸识别系统的一个关键部分&#xff0c;是…
阅读更多...
最新文章

Copyright @ 2022~2023