优选算法之二分查找(上)

目录

一、二分查找

1.题目链接:704. 二分查找

2.题目描述:

3.算法流程:

4.算法代码:

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

1.题目链接:34. 在排序数组中查找元素的第一个和最后一个位置

2.题目描述:

3.算法流程:

4.算法代码:

三、x的平方根

1.题目链接:69. x 的平方根 

2.题目描述:

3.解法一(暴力解法)

🌴算法思路:

🌴算法代码:

4.解法二(二分查找算法)

🌴算法思路:

🌴算法代码:

四、搜索插入位置

1.题目链接:35. 搜索插入位置

2.题目描述:

3.解法(二分查找算法)

🌴算法思路:

🌴算法代码:

五、二分模板


一、二分查找

1.题目链接:704. 二分查找

2.题目描述:

给定一个 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]之间。

3.算法流程:

a. 定义 left , right 指针,分别指向数组的左右区间。

b. 找到待查找区间的中间点 mid ,找到之后分三种情况讨论:

  1. arr[mid] == target 说明正好找到,返回 mid 的值;
  2. arr[mid] > target 说明 [mid, right] 这段区间都是大于 target 的,因此舍去右边区间,在左边 [left, mid -1] 的区间继续查找,即让 right = mid - 1 ,然后重复 2 过程;
  3. arr[mid] < target 说明 [left, mid] 这段区间的值都是小于 target 的,因此舍去左边区间,在右边 [mid + 1, right] 区间继续查找,即让 left = mid + 1 ,然后重复 2 过程;

c. 当 left 与 right 错开时,说明整个区间都没有这个数,返回 -1

4.算法代码:

class Solution 
{
public:int search(vector<int>& nums, int target) {// 初始化 left 与 right 指针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)right = mid - 1;elseleft = mid + 1;}// 如果程序⾛到这⾥,说明没有找到⽬标值,返回 -1return -1;}
};

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

1.题目链接:34. 在排序数组中查找元素的第一个和最后一个位置

2.题目描述:

给你一个按照非递减顺序排列的整数数组 nums,和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target,返回 [-1, -1]

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1:

输入:nums = [5,7,7,8,8,10], target = 8
输出:[3,4]

示例 2:

输入:nums = [5,7,7,8,8,10], target = 6
输出:[-1,-1]

示例 3:

输入:nums = [], target = 0
输出:[-1,-1]

3.算法流程:

        用的还是二分思想,就是根据数据的性质,在某种判断条件下将区间一分为二,然后舍去其中一个区间,然后在另一个区间内查找;为了方便叙述,我们用 x 表示该元素, resLeft 表示左边界, resRight 表示右边界。


寻找左边界思路:

🌵寻找左边界:

我们注意到以左边界划分的两个区间的特点为:

  • 左边区间 [left, resLeft - 1] 都是小于 x 的;
  • 右边区间(包括左边界) [resLeft, right] 都是大于等于 x 的;

🌵因此,关于 mid 的落点,我们可以分为下面两种情况:

  • 当我们的 mid 落在 [left, resLeft - 1] 区间的时候,也就是 arr[mid] <target 。说明 [left, mid] 都是可以舍去的,此时更新 left 到 mid + 1 的位置,继续在 [mid + 1, right] 上寻找左边界;
  • 当 mid 落在 [resLeft, right] 的区间的时候,也就是 arr[mid] >= target 。说明 [mid + 1, right] (因为 mid 可能是最终结果,不能舍去)是可以舍去的,此时更新 right 到 mid 的位置,继续在 [left, mid] 上寻找左边界;

🌵由此,就可以通过二分,来快速寻找左边界;

注意:这里找中间元素需要向下取整。因为后续移动左右指针的时候:

  • 左指针: left = mid + 1 ,是会向后移动的,因此区间是会缩小的;
  • 右指针: right = mid ,可能会原地踏步(比如:如果向上取整的话,如果剩下 1,2 两个元素, left == 1 , right == 2 , mid == 2 。更新区间之后, left,right,mid 的值没有改变,就会陷入死循环)。

因此⼀定要注意,当 right = mid 的时候,要向下取整。


寻找右边界思路:

🌴寻找右边界:

用 resRight 表示右边界;我们注意到右边界的特点为:

  • 左边区间 (包括右边界) [left, resRight] 都是小于等于 x 的;
  • 右边区间 [resRight+ 1, right] 都是大于 x 的;

🌴因此,关于 mid 的落点,我们可以分为下面两种情况:

  • 当我们的 mid 落在 [left, resRight] 区间的时候,说明 [left, mid - 1]( mid 不可以舍去,因为有可能是最终结果) 都是可以舍去的,此时更新 left 到 mid的位置;
  • 当 mid 落在 [resRight+ 1, right] 的区间的时候,说明 [mid, right] 内的元素是可以舍去的,此时更新 right 到 mid - 1 的位置;

🌴由此,就可以通过二分,来快速寻找右边界;

注意:这里找中间元素需要向上取整。因为后续移动左右指针的时候:

  • 左指针: left = mid ,可能会原地踏步(比如:如果向下取整的话,如果剩下 1,2 两个元素, left == 1, right == 2,mid == 1 。更新区间之后, left,right,mid 的值没有改变,就会陷入死循环)。
  • 右指针: right = mid - 1 ,是会向前移动的,因此区间是会缩小的;

因此一定要注意,当 right = mid 的时候,要向下取整。

4.算法代码:

class Solution
{
public:vector<int> searchRange(vector<int>& nums, int target) {// 处理边界情况if(nums.size() == 0) return {-1, -1};int begin = 0;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 {-1, -1};else begin = 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};}
};

三、x的平方根

1.题目链接:69. x 的平方根 

2.题目描述:

给你一个非负整数 x ,计算并返回 x 的 算术平方根 。

由于返回类型是整数,结果只保留 整数部分 ,小数部分将被 舍去 。

注意:不允许使用任何内置指数函数和算符,例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1:

输入:x = 4
输出:2

示例 2:

输入:x = 8
输出:2
解释:8 的算术平方根是 2.82842..., 由于返回类型是整数,小数部分将被舍去。

3.解法一(暴力解法

🌴算法思路:

        依次枚举 [0, x] 之间的所有数 i :(这里没有必要研究是否枚举到 x / 2 还是 x / 2 + 1 。因为我们找到结果之后直接就返回了,往后的情况就不会再判断。反而研究枚举区间,既耽误时间,又可能出错)

  • 如果 i * i == x ,直接返回 x ;
  • 如果 i * i > x ,说明之前的一个数是结果,返回 i - 1 。 由于 i * i 可能超过 int 的最大值,因此使用 long long 类型。

🌴算法代码:

class Solution 
{
public:int mySqrt(int x) {// 由于两个较⼤的数相乘可能会超过 int 最⼤范围// 因此⽤ long longlong long i = 0;for(i = 0; i <= x; i++){// 如果两个数相乘正好等于 x,直接返回 iif(i * i == x)return i;// 如果第⼀次出现两个数相乘⼤于 x,说明结果是前⼀个数if(i * i > x)return i - 1;}// 为了处理oj题需要控制所有路径都有返回值return -1;}
};

4.解法二(二分查找算法

🌴算法思路:

设 x 的平方根的最终结果为 index :

分析 index 左右两侧数据的特点:

  • [0, index] 之间的元素,平方之后都是小于等于 x 的;
  • [index + 1, x] 之间的元素,平方之后都是x 的。
  • 因此可以使用二分查找算法。

🌴算法代码:

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 right;}
};

四、搜索插入位置

1.题目链接:35. 搜索插入位置

2.题目描述:

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例 1: 

输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:

输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:

输入: nums = [1,3,5,6], target = 7
输出: 4

3.解法(二分查找算法

🌴算法思路:

a. 分析插入位置左右两侧区间上元素的特点:
设插入位置的坐标为 index ,根据插入位置的特点可以知道:

  • [left, index - 1] 内的所有元素均是小于 target 的;
  • [index, right] 内的所有元素均是大于等于 target 的。

b. 设 left 为本轮查询的左边界, right 为本轮查询的右边界。根据 mid 位置元素的信息,分析下⼀轮查询的区间:

  • 当 nums[mid] >= target 时,说明 mid 落在了 [index, right] 区间上,mid 左边包括 mid 本身,可能是最终结果,所以我们接下来查找的区间在 [left,mid] 上。因此,更新 right 到 mid 位置,继续查找。
  • 当 nums[mid] < target 时,说明 mid 落在了 [left, index - 1] 区间上,mid 右边但不包括 mid 本身,可能是最终结果,所以我们接下来查找的区间在 [mid + 1, right] 上。因此,更新 left 到 mid + 1 的位置,继续查找。

c. 直到我们的查找区间的长度变为 1 ,也就是 left == right 的时候, left 或者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) / 2;if(nums[mid] < target)left = mid + 1;elseright = mid;}if(nums[left] < target) return left + 1;return left;}
};

五、二分模板

在求 mid 的时候,只有 right - 1 的情况下,才会向上取整(也就是 +1 取中间数)。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

大语言模型-RetroMAE-检索预训练模型

一、背景信息&#xff1a; RetroMAE是2022年10月由北邮和华为提出的一种密集检索预训练策略。 RetroMAE主要应用于检索模型的预训练&#xff0c;模型架构为非对称的Encoder-Decode结构。 二、整体结构&#xff1a; RetroMAE的模型架构为非对称的Encoder-Decode结构。 Encod…

Linux嵌入式学习——数据结构——概念和Seqlist

数据结构 相互之间存在一种或多种特定关系的数据元素的集合。 逻辑结构 集合&#xff0c;所有数据在同一个集合中&#xff0c;关系平等。 线性&#xff0c;数据和数据之间是一对一的关系。数组就是线性表的一种。 树&#xff0c; 一对多 图&#xff0c;多对多 …

k8s中部署Jenkins、SonarQube、StorageClass部署流程

部署Jenkins 系统环境&#xff1a; • kubernetes 版本&#xff1a;1.23.3 • jenkins 版本&#xff1a;2.172 • jenkins 部署示例文件 Github 地址&#xff1a;https://github.com/my-dlq/blog-example/tree/master/jenkins-deploy 一、设置存储目录 在 Kubenetes 环境下…

机器学习·概率论基础

概率论 概率基础 这部分太简单&#xff0c;直接略过 条件概率 独立性 独立事件A和B的交集如下 非独立事件 非独立事件A和B的交集如下 贝叶斯定理 先验 事件 后验 在概率论和统计学中&#xff0c;先验概率和后验概率是贝叶斯统计的核心概念 简单来说后验概率就是结合了先验概…

【SpingCloud】客户端与服务端负载均衡机制,微服务负载均衡NacosLoadBalancer, 拓展:OSI七层网络模型

客户端与服务端负载均衡机制 可能有第一次听说集群和负载均衡&#xff0c;所以呢&#xff0c;我们先来做一个介绍&#xff0c;然后再聊服务端与客户端的负载均衡区别。 集群与负载均衡 负载均衡是基于集群的&#xff0c;如果没有集群&#xff0c;则没有负载均衡这一个说法。 …

springcolud学习05Feign

Feign Feign是一个声明式的http客户端,我们知道,在不使用Feign之前,在微服务中,一个模块如果想要调用另一个模块中的某个功能,需要向其发起请求http请求,如果不使用Feign,我们就需要通过硬编码的形式去编写构建http请求 新建模型,建立一个和consumer一样的module,不…

Python 实现PDF和TIFF图像之间的相互转换

PDF是数据文档管理领域常用格式之一&#xff0c;主要用于存储和共享包含文本、图像、表格、链接等的复杂文档。而TIFF&#xff08;Tagged Image File Format&#xff09;常见于图像处理领域&#xff0c;主要用于高质量的图像文件存储。 在实际应用中&#xff0c;我们可能有时需…

leetcode算法题之接雨水

这是一道很经典的题目&#xff0c;问题如下&#xff1a; 题目地址 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图&#xff0c;计算按此排列的柱子&#xff0c;下雨之后能接多少雨水。 解法1&#xff1a;动态规划 动态规划的核心就是将问题拆分成若干个子问题求解&#…

TCP与UDP网络编程

网络通信协议 java.net 包中提供了两种常见的网络协议的支持: UDP&#xff1a;用户数据报协议(User Datagram Protocol)TCP&#xff1a;传输控制协议(Transmission Control Protocol) TCP协议与UDP协议 TCP协议 TCP协议进行通信的两个应用进程&#xff1a;客户端、服务端 …

GD32相较于STM32的优劣势

优势 1.更高的主频 GD32单片机的主频可以达到108MHz&#xff0c;‌而STM32的最大主频为72MHz&#xff0c;‌这意味着GD32在代码执行速度上具有优势&#xff0c;‌适合需要快速处理数据的场景 2.更低的内核电压 GD32的内核电压为1.2V&#xff0c;‌而STM32的内核电压为1.8V。…

【保姆级介绍服务器硬件的基础知识】

🌈个人主页: 程序员不想敲代码啊 🏆CSDN优质创作者,CSDN实力新星,CSDN博客专家 👍点赞⭐评论⭐收藏 🤝希望本文对您有所裨益,如有不足之处,欢迎在评论区提出指正,让我们共同学习、交流进步! 🦭服务器硬件基础知识 1. 🦭前言2. 🦭中央处理器(CPU)3. 🦭…

LeYOLO, New Scalable and Efficient CNN Architecture for Object Detection

LeYOLO, New Scalable and Efficient CNN Architecture for Object Detection 论文链接&#xff1a;http://arxiv.org/abs/2406.14239 代码链接&#xff1a;https://github.com/LilianHollard/LeYOLO 一、介绍 本文关注基于FLOP的高效目标检测计算的神经网络架构设计选择&am…

STM32CUBEIDE FreeRTOS操作教程(一):LED闪灯

STM32CUBEIDE FreeRTOS操作教程&#xff08;一&#xff09;&#xff1a;LED闪灯 STM32CUBEIDE(不是STM32CUBEMX)开发环境集成了STM32 HAL库进行FreeRTOS配置和开发的组件&#xff0c;不需要用户自己进行FreeRTOS的移植。这里介绍最简化的用户操作类应用教程。以STM32F401RCT6开…

利用PyTorch进行模型量化

利用PyTorch进行模型量化 目录 利用PyTorch进行模型量化 一、模型量化概述 1.为什么需要模型量化&#xff1f; 2.模型量化的挑战 二、使用PyTorch进行模型量化 1.PyTorch的量化优势 2.准备工作 3.选择要量化的模型 4.量化前的准备工作 三、PyTorch的量化工具包 1.介…

微软的Edge浏览器如何设置兼容模式

微软的Edge浏览器如何设置兼容模式&#xff1f; Microsoft Edge 在浏览部分网站的时候&#xff0c;会被标记为不兼容&#xff0c;会有此网站需要Internet Explorer的提示&#xff0c;虽然可以手动点击在 Microsoft Edge 中继续浏览&#xff0c;但是操作起来相对复杂&#xff0c…

【BUG】已解决:Downgrade the protobuf package to 3.20.x or lower.

Downgrade the protobuf package to 3.20.x or lower. 目录 Downgrade the protobuf package to 3.20.x or lower. 【常见模块错误】 【解决方案】 欢迎来到英杰社区https://bbs.csdn.net/topics/617804998 欢迎来到我的主页&#xff0c;我是博主英杰&#xff0c;211科班出身…

Stable Diffusion基本原理通俗讲解

Stable Diffusion是一种基于深度学习的图像生成技术&#xff0c;它属于生成对抗网络&#xff08;GANs&#xff09;的一种。简单来说&#xff0c;Stable Diffusion通过训练一个生成器&#xff08;Generator&#xff09;和一个判别器&#xff08;Discriminator&#xff09;&#…

Vue使用FullCalendar实现日历/周历/月历

Vue使用FullCalendar实现日历/周历/月历 需求背景&#xff1a;项目上遇到新需求&#xff0c;要求实现工单以日/周/月历形式展示。而且要求不同工单根据状态显示不同颜色&#xff0c;一个工单内部&#xff0c;需要以不同颜色显示三个阶段。 效果图 日历 周历 月历 安装插件…

【unity 新手教程 001/100】安装与窗口布局介绍

欢迎关注 、订阅专栏 【unity 新手教程】谢谢你的支持&#xff01;&#x1f49c;&#x1f49c; Unity下载与安装 &#x1f449;点击跳转详细图文步骤&#xff1a;Unity Hub Unity 编辑器 窗口布局&#xff1a; Hierarchy: 层级窗口 | 默认 Sample Scene (main camera、direc…

75.WEB渗透测试-信息收集- WAF、框架组件识别(15)

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 内容参考于&#xff1a; 易锦网校会员专享课 上一个内容&#xff1a;74.WEB渗透测试-信息收集- WAF、框架组件识别&#xff08;14&#xff09; php常见的组件…