【基础算法总结】二分查找二

news/2024/9/19 20:30:34/ 标签: 算法

二分查找二

  • 1.山脉数组的峰顶索引
  • 2.寻找峰值
  • 3.寻找旋转排序数组中的最小值
  • 4.点名

在这里插入图片描述

点赞👍👍收藏🌟🌟关注💖💖
你的支持是对我最大的鼓励,我们一起努力吧!😃😃

1.山脉数组的峰顶索引

题目链接:852. 山脉数组的峰顶索引

题目描述:

在这里插入图片描述

题目描述的有些复杂,换成图形就是一个山峰让你找最顶点
在这里插入图片描述
算法原理:

首先我们会想到遍历,找到这个数组中第一次出现当前这个值比下一个值大的下标,

解法一:暴力枚举 O(N)

题目要求O(logn),我们看看有没有优化的地方。我们发现这个峰顶值把数组分成了两部分,这时你会想到什么 二段性
在这里插入图片描述
解法二:二分查找算法

在这里插入图片描述

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;else right=mid-1;}return left;}
};

2.寻找峰值

题目链接:162. 寻找峰值

题目描述:

在这里插入图片描述

这道题也是找峰值但是和上面不一样的是上面那道题数组就是上下一种情况,而这里数组可能会有三种情况:

在这里插入图片描述

算法原理:

解法一:暴力求解 O(N)
从第一个位置开始,一直往后走,分情况讨论即可

分析一下有没有优化的地方。因为我们就是比较当前位置和下一个位置的关系,所以我们把这个数组抽象出来。

在这里插入图片描述

  1. arr[i] > arr[i+1] ,此时是一个下降趋势,左边区间一定会存在一个峰值,左右都是负无穷,左边是从负无穷开始的,呈现上升趋势然后才下降,所以左边一定是有峰值的。但是右边区间不一定,因为右边是负无穷可能一直下降。接下来去左边寻找。
  2. arr[i] < arr[i+1],此时是一个上升趋势,左边是从服务器开始可能一直在上升,那可能是没有最终结果的。但是右边一定是有最终结果的,因为右边是负无穷,会降到负无穷的。接下来去右边寻找。

我们发现这两个点的关系把整个数组分成了两部分。然后我们去一个部分去搜索结果。

解法二:二分查找
这道题是严格无序的,因为可能存在一升一降、一升一降。但是我们找到了二段性,因此也可以用二分查找算法

在这里插入图片描述

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]) right=mid;else left=mid+1;}return left;}
};

3.寻找旋转排序数组中的最小值

题目链接:153. 寻找旋转排序数组中的最小值

题目描述:

在这里插入图片描述
注意题目给的是 互不相同 的元素
在这里插入图片描述
算法原理:

这道题暴力求解很容易想到办法,从前往后遍历然后找最小值就可以了

解法一:暴力求解 O(N)

但是我们观察之后,发现这个数组可以分成两段。A-B 递增 C-D也是递增。
假设我们已D为分割点,我们发现A-B内的值大于D,C-D内的值小于等于D。由此我们发现了二段性
在这里插入图片描述

解法二:二分查找算法

在这里插入图片描述

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

上面我们以D为分割点,那以A点为分割点可不可以?其实也是可以的,但是要注意可以旋转之后是一个严格递增的数组,这里要特别处理一下。以D为分割点不会碰到这个问题。可以自己分析一波
在这里插入图片描述

class Solution {
public:int findMin(vector<int>& nums) {int left=0,right=nums.size()-1;int n=right;while(left<right){int mid=left+(right-left)/2;if(nums[mid]>=nums[0]) left=mid+1;else right=mid;}//旋转后严格单调递增if(nums[left]>nums[0]) return nums[0];return nums[left];}
};

4.点名

题目链接:LCR 173. 点名

题目描述:

在这里插入图片描述
算法原理:

这道题很简单,总要考察的是对于一种题你有几个解题思路

解法一:哈希表 时间O(N) 空间O(N)
把数组中所有数映射进hash表

class Solution {
public:int takeAttendance(vector<int>& records) {//1.哈希表int n=records.size()+1;int hash[10001]={0};for(int i=0;i<records.size();++i){hash[records[i]]++;}for(int i=0;i<n;++i){if(hash[i]==0) return i;}}
};

解法二:暴力遍历 O(N)

class Solution {
public:int takeAttendance(vector<int>& records) {//2.暴力遍历int n=0;for(int i=0;i<records.size();i++){if(records[i] != n) break;++n;}return n;}
};

解法三:位运算

将缺少的上面和不缺少的下面进行异或运算。异或运算相同为0,相异为1。最终会有正确结果。具体操作是将数字和下标异或,最后在异或一次就可以了
在这里插入图片描述

class Solution {
public:int takeAttendance(vector<int>& records) {//3.位运算int x = 0;for (int i = 0; i < records.size(); i++)x ^= records[i] ^ i ;return x^records.size();}
};

解法四:等差数列求和

class Solution {
public:int takeAttendance(vector<int>& records) {//4.求和公式int n = records.size();int sum = (1+n)*n/2;for(int i = 0;i<records.size();++i){sum-=records[i];}return sum;}
};

上面时间复杂度都是O(N),思考一下看看有没有优化的可能

在这里插入图片描述
由此发现二段性

解法五:二分查找算法
在这里插入图片描述

class Solution {
public:int takeAttendance(vector<int>& records) {//0.二分查找int left=0,right=records.size()-1;while(left<right){int mid=left+(right-left)/2;if(records[mid]==mid) left=mid+1;else right=mid;}if(left == records[left]) return left+1;else return left;}
};

http://www.ppmy.cn/news/1462014.html

相关文章

汇编个位数求和实验

title: 汇编求和实验 keywords: 汇编 tags: [汇编] categories: 嵌入式 汇编求和实验 刚开始学习汇编 给大家做个参考 实验 5 子程序 5.1 实验目的 ①掌握利用堆栈传递参数的子程序调用方法。 ②过程调用伪指令&#xff1a;PROC&#xff0c;ENDP&#xff0c;NEAR和FAR。 ③8088…

Tomcat闪退

Tomcat闪退可能由多种原因引起&#xff0c;包括内存不足、程序异常、端口冲突、配置文件错误、版本不兼容、硬件故障等。以下是一些解决Tomcat闪退问题的常见方法&#xff1a; 检查内存&#xff1a;Tomcat运行需要大量的内存资源。如果服务器内存不足&#xff0c;可以尝试增加…

探测器 烟尘水汽 笔记

目录 探测器穿透水汽 1. 毫米波雷达 2. 红外摄像机 3. LIDAR&#xff08;光检测与测距&#xff09; 4. 热成像仪 5. 超声波传感器 探测器穿透烟尘 探测器穿透水汽 能穿透水汽的探测设备主要包括使用特定波段的雷达和红外技术的设备。这些技术能有效应对由雾、雨、水汽等…

Rust Web开发框架actix-web入门案例

概述 在看书的时候&#xff0c;用到了actix-web这个框架的案例。 书里面的版本是1.0&#xff0c;但是我看官网最新都4.4了。 为了抹平这种信息差&#xff0c;所以我决定把官方提供的示例代码过一遍。 核心代码 Cargo.toml [package] name "hello" version &q…

GPT-4o“成精了”:推测技术原理,附送“美国湾区”小道消息

原创&#xff1a;谭婧 如果你能跟上技术发展&#xff0c;那大多数技术提升都是按部就班&#xff0c; 偶而会有突破性进展。 如果你仅仅吃瓜&#xff0c;那OpenAI的所有新闻&#xff0c; 你都可以写成&#xff1a; “改写历史”“干翻所有”“颠覆世界”。 真的颠覆世界了吗&…

Hello, GPT-4o!

2024年5月13日&#xff0c;OpenAI 在官网正式发布了最新的旗舰模型 GPT-4o 它是一个 多模态模型&#xff0c;可以实时推理音频、视频和文本。 * 发布会完整版视频回顾&#xff1a;https://www.youtube.com/watch?vDQacCB9tDaw GPT-4o&#xff08;“o”代表“omni”&#xff0c…

【会议征稿】2024年机器人前沿技术与创新国际会议(FTIR 2024, 7/19-21)

2024年机器人前沿技术与创新国际会议&#xff08;FTIR 2024&#xff09;将于2024年7月19-21日在中国杭州举行。FTIR 2024聚焦前沿技术与创新&#xff0c;将把机器人领域的创新学者和专家聚集到一个共同的论坛。会议的主要目标是促进机器人的研究和开发活动&#xff0c;另一个目…

Qt三方库:QuaZIP介绍、编译和使用

前言 Qt使用一些压缩解压功能&#xff0c;探讨过libzip库&#xff0c;zlib库&#xff0c;libzip库比较原始&#xff0c;还有其他库&#xff0c;都比较基础&#xff0c;而在基础库之上&#xff0c;又有高级封装库&#xff0c;Qt中的QuaZIP是一个很好的选择。Quazip是一个用于压缩…

yolov9训练自定义数据

1.训练yolov9&#xff0c;先准备好一份自定义数据.。到roboflow下载一份数据&#xff0c;数据格式是yolo格式。 2.到github下载yolov9源码 https://github.com/WongKinYiu/yolov9 3.为了方便配置环境&#xff0c;把代码上传到矩池云上面&#xff0c;使用云服务器 4.执行 pip i…

【Bug】Clash出现端口0的情况

win版本的Docker桌面版用了Hyper-V的功能&#xff0c;虚拟机需要映射一部分端口&#xff0c;并且在系统更新后对动态映射的端口范围进行了更改&#xff0c;导致占用了本来的7890Clash使用的端口。 cmd去查看还能使用的端口 netsh interface ipv4 show excludedportrange prot…

ArcGI基本技巧-科研常用OLS, GWR, GTWR模型实现

ArcGI基本技巧-科研常用OLS, GWR, GTWR模型实现 OLS,GWR,GTWR回归模型均可以揭示解释变量对被解释变量的影响且可以进行预测。Ordinary Least Squares (OLS)是最小二乘法&#xff0c;Geographically Weighted Regression (GWR)是地理加权回归&#xff0c;Geographically and T…

openFeign 调用后 返回 出现 application/json 错误

项目场景&#xff1a; 远程调用时返回json格式错误 项目场景&#xff1a;从分页插件式改换为原生分页的时候 通过openFeign调用时发现了问题 问题描述 不需要openFeign 调用的时候 返回的数据和格式是对 通过openFeign 调用后返回 出现 application/json 错误 &#xff1a; …

代码随想录--链表--反转链表

题目 题意&#xff1a;反转一个单链表。 示例: 输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL 思路 如果再定义一个新的链表&#xff0c;实现链表元素的反转&#xff0c;其实这是对内存空间的浪费。 其实只需要改变链表的next指针的…

AI4Science

AI4Science 文章目录 AI4ScienceMicroSoft AI4Science其它 微软研究院刘铁岩&#xff1a;AI for Science&#xff0c;追求人类智能最光辉的一面&#xff5c;MEET2023 &#xff08;17min&#xff09; https://www.bilibili.com/video/BV1bs4y1W7rW/AI Forum 2023 | AI4Science: …

项目-坦克大战

增加功能 我方坦克在发射的子弹消亡后&#xff0c;才能发射新的子弹。同时实现发多颗子弹 1&#xff0c;在按下J键&#xff0c;我们判断当前hero对象的子弹&#xff0c;是否已经销毁2&#xff0c;如果没有销毁&#xff0c;就不去触发shotEnemyTank3&#xff0c;如果已经销毁&…

Android系统不同版本存储权限

一、Android存储简介 Android系统分为内部存储和外部存储 从Android6.0开始不断在更新存储&#xff08;读写&#xff09;权限&#xff0c;除了在AndroidManifest.xml文件里声明&#xff0c;app运行时也要动态申请使用对应的权限 提醒&#xff1a;应用私有存储不需要动态申请权…

AtCoder Beginner Contest 318 A题 Full Moon

A题&#xff1a;Full Moon 标签&#xff1a;模拟、数学题意&#xff1a;给定一个起始 m m m和上限 n n n&#xff0c;每次增量 p p p&#xff0c;求能加几次。题解&#xff1a;数据比较小&#xff0c;可以直接暴力&#xff1b;数学方法算的话&#xff0c;注意边界。代码&#…

2024数维杯数学建模C题思路代码

2024年数维杯&电工杯思路代码在线文档​https://www.kdocs.cn/l/cdlol5FlRAdE 这道题想要做出好的结果&#xff0c;必须要结合插值法和分布函数来做&#xff0c;主要还是因为勘探点太少&#xff0c;直接用插值法效果不太好&#xff0c;以下是我做的&#xff0c;函数分布可…

AMD W7900本地大型语言模型的微调

GenAI-contest/01-LLM_Fine-tuning at main amd/GenAI-contest (github.com) 大型语言模型&#xff08;LLMs&#xff09;在大量的文本数据上进行训练。因此&#xff0c;它们能够生成连贯且流畅的文本。Transformer架构是所有LLMs的基础构建块&#xff0c;它作为底层架构&…

快速掌握Spring底层原理整体脉络

快速掌握Spring底层原理整体脉络 介绍 在Java开发领域&#xff0c;Spring框架是一个非常流行的选择。作为一名Java架构师&#xff0c;了解Spring底层原理是非常重要的。本文将帮助你快速掌握Spring底层原理的整体脉络&#xff0c;让你更好地理解和应用Spring框架。 Spring框…