二分算法——优选算法

ops/2024/9/22 16:06:26/

个人主页:敲上瘾-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/ops/114311.html

相关文章

完整版:NacosDocker 安装

第一步&#xff1a;先直接通过命令安装 Nacos docker run --name nacos2.2.3 -d -p 8848:8848 -e MODEstandalone f151dab7a111 第二步&#xff1a;创建 Docker 挂载目录 # 创建 log 目录 mkdir -p /root/nacos 第三步&#xff1a;将 Docker 容器的文件复制到挂载目录中 …

剖解反转链表

剖解反转链表 思路&#xff1a; 1.若链表为空或者只存在一个节点&#xff0c;就无需反转&#xff0c;直接返回head 2.若存在多个节点 首先将head.next给到cur&#xff0c;并将head.next置为null 剩余的节点就利用头插法&#xff0c;反转链表 class Solution {public ListNo…

SpringBoot 更改启动图标

每次springboot开启时&#xff0c;开会显示spring的图标&#xff0c;这个图标是可以修改的。 一、原始的图标样式 二、修改图标样式 https://patorjk.com/software/taag/#pdisplay&fGraffiti&thttps://patorjk.com/software/taag/#pdisplay&fGraffiti&t 在…

Day 9:1306 跳跃游戏III

1306 跳跃游戏III 1. 题目描述2. 解题思路3. 代码实现(DFS)4. 代码实现(BFS) 1. 题目描述 1306 跳跃游戏III 2. 解题思路 使用dfs或bfs的思想来进行遍历;使用used数组来表示当前位置是否被访问过。 3. 代码实现(DFS) class Solution { public:bool canReach(vector<int…

PostgreSQL维护——解决索引膨胀和数据死行

注意&#xff1a; 本文内容于 2024-09-16 00:40:33 创建&#xff0c;可能不会在此平台上进行更新。如果您希望查看最新版本或更多相关内容&#xff0c;请访问原文地址&#xff1a;PostgreSQL维护——解决索引膨胀和数据死行。感谢您的关注与支持&#xff01; 我有一张表&#…

特殊类的设计与类型转换

特殊类的设计 1.请设计一个不能被拷贝的类 拷贝只会放生在两个场景中&#xff1a;拷贝构造函数以及赋值运算符重载&#xff0c;因此想要让一个类禁止拷贝&#xff0c;只需让该类不能调用拷贝构造函数以及赋值运算符重载即可。 C98 C98是怎么设计的呢&#xff1f; class Cop…

音视频生态下Unity3D和虚幻引擎(Unreal Engine)的区别

技术背景 好多开发者跟我们做技术交流的时候&#xff0c;会问我们&#xff0c;为什么有Unity3D的RTMP|RTSP播放模块&#xff0c;还有RTMP推送和轻量级RTSP服务模块&#xff0c;为什么不去支持虚幻引擎&#xff1f;二者区别在哪里&#xff1f;本文就Unity3D和虚幻引擎之间的差异…

万能头无法使用

打开 新建 工具 编辑器选项 代码 这个缺省源 复制上这个 #ifndef _GLIBCXX_NO_ASSERT #include <cassert> #endif #include <cctype> #include <cerrno> #include <cfloat> #include <ciso646> #include <climits> #include <clocale&…