二分算法——优选算法

embedded/2024/11/14 12:48:18/

个人主页:敲上瘾-CSDN博客

个人专栏:游戏、数据结构、c语言基础、c++学习、算法

        本章我们来学习的是二分查找算法,二分算法的应用非常广泛,不仅限于数组查找,还可以用于解决各种搜索问题、查找极值问题等。在数据结构算法中,它是基础且重要的算法之一。

接下来我准备了三个题来引出并学习该算法,最后来做总结。

目录

一、二分查找

1.题目解析

2.算法原理

3.代码编写

二、查找元素的首末位置

1.题目解析

2.算法原理

3.代码编写

三、寻找峰值

1.题目解析

2.算法原理

3.代码编写

四、总结


一、二分查找

1.题目解析

        该题目要求是给一个元素target然后在升序数组nums中找到该元素的下标,若不存在则返回-1。题目要求简单易懂就不再多讲,这里要注意两个点:(1)、数组是升序的。(2)、需要返回的是元素下标。

2.算法原理

        对于该题最容易想到的解法就是把数组从头到尾遍历一遍,时间复杂度为O(N)。

        解法二:因为这个数组是有序的所以我们可以用二分的思想,首先使用三个指针(这里指的是数组的下标)left,right,mid,其中left和right维护一段区间,把目标值锁定到[left,right]区间内。mid表示区间的中心下标,把区间一分为二。

        接下来锁定target的位置:如果target小于mid下标指向的元素,那么因为数组是升序,所以target一定在区间[left,mid]中,即right更新为mid,然后更新mid( mid=left+(right-left)/2 )。              如果target大于mid指向元素,那么target一定在区间[mid,right]中,即把left更新为mid,然后更新mid。重复操作直到left>right。

如下:

算法的时间复杂度为logN,证明如下:

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

二、查找元素的首末位置

1.题目解析

        该题的题目要求与上一题类似,都是在升序数组中查找元素,不过该题查找的是元素第一次出现的位置和最后一次出现的位置。这里还要求时间复杂度为O(logN),这里就很明显地提示了该题要使用二分算法

2.算法原理

        同样的此题可以使用暴力枚举来解决,不过时间复杂度为O(N),根据上题的经验这里我们还是考虑使用二分法。不过也很容易发现把上面的算法原模原样搬过来是解决不了该道题的,我们只能找到target元素的是无法锁定它第一次出现的位置和最后一次出现的位置。我们可以用以下解法:

左边界查找:

        当mid指向的元素为target的时候,不用返回,而是让right更新为mid,mid指向元素大于target时同样更新right为mid,即可以合并为

        if(nums[mid]>=target)   right=mid;

当mid指向元素小于target时left更新为mid+1,重复该操作就可以把数组右边的target忽略,锁定最左边的target。这里做循环的时候需要注意循环条件不能是left<=rigth,如果是left<=right就可能使mid一直赋值给right从而进入死循环,所以我们使用left<right

右边界查找:

        当mid指向的元素为target的时候,不用返回,而是让left更新为mid,mid指向元素小于target时同样更新left为mid,即可以合并为

        if(nums[mid]<=target)   left=mid;

当mid指向元素大于target时right更新为mid-1,重复该操作就可以把数组左边的target忽略,锁定最右边的target。这里做循环的时候同样需要注意循环条件只能是left<rigth。

注意:当元素只有两个时使用mid=left+(right-left)/2计算的mid就是第一个元素,那么也就是mid==left,如果mid指向的元素为target时把mid赋值给left(即left=mid)相当于什么也没干,程序同样会进入死循环。所以我们使用mid=left+(right-left+1)/2计算mid。

        以上的两个查找法几乎可以解决所有的二分算法题,可以作为一个模板记忆,在总结部分我会给出模板。

3.代码编写

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;while(left<right){int mid=left+(right-left)/2;if(nums[mid]>=target) right=mid;else left=mid+1;}if(nums[left]!=target) return {-1,-1};int n=left;right=nums.size()-1;while(left<right){int mid=left+(right-left+1)/2;if(nums[mid]<=target) left=mid;else right=mid-1;}return {n,left};}
};

三、寻找峰值

1.题目解析

该题要求我们返回任意峰值,比如把数组元素抽象成连续的数据如下:

需要返回以上红圈部分的任意一点, 也就是该元素至少要满足它左边的第一个元素和右边的第一个元素都要小于它。

注意:题目给的信息nums[-1]和nums[n]为负无穷,所以不要忽略以下情况:

2.算法原理

        这题同样可以使用暴力枚举,时间复杂度为O(N),该解法就不再多讲。

        这个题与上两个题有一个很大的区别是该数组并不是有序的,但是没关系该题同样可以使用二分的思想,注意很多人会误认为二分算法只能用在有序的数组中,而事实并不局限于此,只需要找到数据的二段性即可,如该题我们可以这样:

        该方法也就是上一题的右边界查找,当然也可以使用左边界查找的方法,但用朴素的二分查找解决不了该题。

3.代码编写

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

四、总结

1、二分算法并不局限于数组有序,只要找到数据的二段性即可使用二分算法

2、二分算法模板

2.1.朴素二分模板

while(left<=right)
{int mid=left+(right-left)/2;if(...) left=mid+1;else if(...) right=mid-1;else ...
}

2.2.左边界查找模板

while(left<right)
{int mid=left+(right-left)/2;if(...) left=mid+1;else right=mid;
}

2.3.右边界查找模板

while(left<right)
{int mid=left+(right-left+1)/2;if(...) left=mid;else right=mid-1;
}

http://www.ppmy.cn/embedded/114067.html

相关文章

GPT-4论文阅读

GPT-4 Technical Report论文阅读 文章目录 GPT-4 Technical Report论文阅读 Abstract训练的稳定性Training processPredictable scaling训练的稳定性多么难能可贵 Capabilities考试成绩传统的benchmark语言方面的能力Visual inputsSteerability LimitationsRisks & mitigat…

PHP邮箱系统:从入门到实战搭建教程指南!

PHP邮箱系统配置教程&#xff1f;如何选用合适的PHP邮箱系统库&#xff1f; 为了满足个性化和定制化的需求&#xff0c;许多开发者选择使用PHP来搭建自己的邮箱系统。AokSend将带你从入门到实战&#xff0c;详细介绍如何搭建一个功能完善的PHP邮箱系统。 PHP邮箱系统&#xf…

【计算机网络】TCP 协议——详解三次握手与四次挥手

文章目录 一、引言二、TCP1、TCP 的数据格式2、TCP 的三次握手3、TCP 的四次挥手4、TCP 的全双工通信 三、TCP 的状态转换1、TCP 连接的建立&#xff08;三次握手&#xff09;状态2、TCP 连接的终止&#xff08;四次挥手&#xff09;状态3、TCP 异常情况 一、引言 TCP与UDP的区…

系统架构设计师教程 第5章 5.3 系统分析与设计 笔记

5.3 系统分析与设计 系统分析阶段把复杂的对象分解为简单的组成部分&#xff0c;其基本任务是在充分了解用户需求的基础上&#xff0c;书写系统需求规格说明书。 系统设计是根据系统分析的结果&#xff0c;完成系统的构建过程。其主要目的是绘制系统的蓝图&#xff0c;权衡和比…

【macOS】【Python】安装Python到虚拟环境的命令

【macOS】【Python】安装Python到虚拟环境的命令 这个命令是什么意思&#xff1a;conda create -n codeformer python3.8 -y 解读命令 conda create -n codeformer python3.8 -y 1.命令含义 这个命令是使用conda创建一个名为codeformer的虚拟环境&#xff0c; 并且在这个环境…

MacOS Catalina 从源码构建Qt6.2开发库之01: 编译Qt6.2源代码

#!/bin/bash # 设置脚本在遇到错误时立即退出 set -e # 安装Xcode命令行工具 xcode-select --install # 安装依赖项 brew install cmake ninja # 下载Qt6.2源码 git clone https://github.com/qt/qt6-meta.git qt6 cd qt6 # 检出Qt6.2的特定分支 git checkout remotes/o…

Robot Operating System——32 位浮点数表示的三维空间中一个点

大纲 应用场景1. 点云数据处理场景描述具体应用 2. 机器人导航与避障场景描述具体应用 3. 无人机飞行控制场景描述具体应用 4. 机械臂运动控制场景描述具体应用 5. 自动驾驶车辆控制场景描述具体应用 6. 机器人仿真场景描述具体应用 定义字段解释 案例 geometry_msgs::msg::Poi…

机器学习和深度学习区别

机器学习和深度学习作为人工智能领域的两大重要分支&#xff0c;虽然有着紧密的联系&#xff0c;但在多个方面存在显著的差异。以下将从定义与起源、技术基础、模型复杂度、数据需求、计算资源需求、应用领域以及学习方式与特点等角度&#xff0c;详细阐述机器学习和深度学习的…