创办个人网站,wordpress和论坛整合,做网站的做app的,重庆市建设工程信息网打不开是怎么回事#x1f3ac; 个人主页#xff1a;谁在夜里看海.
#x1f4d6; 个人专栏#xff1a;《C系列》《Linux系列》《算法系列》
⛰️ 一念既出#xff0c;万山无阻 目录
#x1f4d6;一、算法思想
细节问题
#x1f4da;左右临界
#x1f4da;中点选择
#x1f4da;… 个人主页谁在夜里看海. 个人专栏《C系列》《Linux系列》《算法系列》
⛰️ 一念既出万山无阻 目录
一、算法思想
细节问题
左右临界
中点选择
循环条件
二、具体运用
1.⼆分查找
算法思路
算法流程
代码
2.查找元素的第⼀个和最后⼀个位置
算法思路
算法流程
代码
3.x的平⽅根
算法思路
代码
4.⼭峰数组的峰顶
算法思路
算法流程
代码
5.点名
算法思路
代码
三、总结 一、算法思想
二分算法是一种经典的高效查询方法它的核心思想是通过不断将查找范围缩小为一半从而大大减少查找的时间复杂度。
例如在一个有序数组中我们要查找指定元素最简单的方法是遍历数组时间复杂度为O(n) 然而使用二分算法cur每次从待遍历数组的中心位置开始判断元素大小 ① 目标元素说明目标元素在右区间更新cur指向右区间的中心位置 ② 目标元素说明目标元素在左区间更新cur指向左区间的中心位置。 此时最坏情况是遍历log(n)次因此时间复杂度为log(n)这意味着在100万个数中查找目标元素最多只需要遍历20次极大提高了效率。
二分算法的本质思想理解起来并不难但是在具体运用之前我们还需要对二分算法有一个更深入的了解二分算法的细节问题
细节问题
左右临界
在二分算法的具体运用中我们不仅需要一个cur指针指向区间的中点还需要left和right指针标记区间的左右临界位置每次遍历之后都需要对临界位置进行更新更新需要分为三种情况
①目标元素不重复
这种情况是最好处理的每次更新时直接将左指针或右指针指向cur后一个位置或前一个位置即可 ②连续序列的左端点
如果我们要查询的不是一个元素而是一个连续序列的左端点例如在 “1, 3, 5, 6, 6, 7, 9, 10” 中查找元素6的开始位置 这个时候cur等于目标值但是并不是需要的结果此时cur应该继续向左区间移动但是right指针该怎么调整呢 我们可以把数组看成a、b两个区间而我们最终要找的是b区间的左端点: ① cur 目标值cur需要指向右区间的中点而左区间123被排除了所以left指向cur的后一个位置 ② cur 目标值由于我们要找的数连续序列的左端点所以此时cur需要更新到左区间的中点而right需指向原cur位置处当cur目标值时cur可能是最终结果也可能不是所以需要保存当前位置 ③连续序列的右端点
例如在 “1, 3, 5, 6, 6, 7, 9, 10” 中查找元素6的结束位置 同样可以看成a、b两个区间而我们要找的是区间a的右端点 ① cur 目标值cur需要指向左区间的中点而右区间7,9,10被排除了所以right指向cur的前一个位置 ② cur 目标值由于我们要找的数连续序列的右端点所以此时cur需要更新到右区间的中点而left需指向原cur位置处当cur目标值时cur可能是最终结果也可能不是所以需要保存当前位置 中点选择
在实际运用中我们会发现如果序列是偶数中心点位置会有两个此时我们需要考虑选择左中点还是右中点同样分为三种情况
①目标元素不重复
在这种情况下中点的选择不会影响最终结果因为目标元素不重复所以选择左中点或右中点皆可
②连续序列的左端点
在这种情况下左右中点的选择会影响判断看下面这种极端情况 遍历到区间只剩两个元素时cur应该更新成left左中点还是right右中点呢
假如更新成right由于cur目标值right会指向cur(还是原位置)如此一来就会进入死循环cur和right会一直在原地踏步所以cur需要更新成左中点。
③连续序列的左端点
相反地 当查询的是连续序列的右端点时cur需更新成右中点 在实际中时间复杂度为log(n)的算法并不多见因为高效率的同时门槛也越高我们常了解到的二分算法只能在有序数组中使用如果数组无序我们就不能保证目标元素在左或右区间就不能一次排除一般的元素。
循环条件
循环条件是 leftright 还是 leftright ? 其实就是考虑left、right相遇之后要不要进入循环
①目标元素不重复
mid指针每次更新前都会进行一次判断如果不是目标元素则更新继续进入循环当left、right相遇时同样需要进行判断如果还不是目标元素则没有结果这个判断和前面的判断一致不需要特殊处理所以循环条件是leftright。
②目标区间的端点
当left与right相遇后 如果当前值不为目标值那么更新left或right指针会正常退出循环如果当前值是目标值那么left与right指针都会停留在当前位置此时就进入了死循环。为了避免死循环我们需要将循环条件设成leftright并且在循环外部额外判断一次。
❓只能是有序数组吗
✅其实并不是二分算法的巧妙就巧妙在同样适用于一些无序的场景后面会碰到具体例题。
二、具体运用
1.⼆分查找
难度等级⭐⭐⭐
题目链接704. 二分查找 - 力扣LeetCode
题目描述 给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。 示例 1: 输入: nums [-1,0,3,5,9,12], target 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4算法思路
这种情况就是二分查找的基础玩法查找一个不重复的目标元素 从待遍历数组的中心位置开始判断元素大小如果目标值则更新到左区间中点目标值更新到右区间中点。
算法流程
①定义left、right、mid指针mid指向left、right的中点位置左右皆可
②判断mid指向元素 a.目标值right指向mid前一个位置更新mid b.目标值left指向mid后一个位置更新mid c.目标值返回当前位置
③执行到此处说明数组不存在目标值返回空
代码
class Solution {
public:int search(vectorint nums, int target) {int left 0,right nums.size()-1,mid (leftright)/2;while(leftright){if(nums[mid]target) right mid-1;else if(nums[mid]target) left mid1;mid (leftright)/2;if(nums[mid]target) return mid;}return -1;}
};
2.查找元素的第⼀个和最后⼀个位置
难度等级⭐⭐⭐⭐
题目链接34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣LeetCode
题目描述 给你一个按照非递减顺序排列的整数数组 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] 算法思路
这道题目就是查找连续区间的端点的情况查找左右端点需要分别进行。在查找时需要注意细节的处理左右临界的选择、中点的选择 、循环条件leftright
算法流程
找区间左端点
①定义left、right、midmid指向left、right的左中点
②判断mid元素 a.目标值right指向mid后一个位置更新mid b.目标值left指向mid更新mid
③此时left、right相遇进行判断如果目标值记录下标否则返回空
找区间右端点
①定义left、right、midmid指向left、right的右中点
②判断mid元素 a.目标值left指向mid前一个位置更新mid b.目标值right指向mid更新mid
③此时left、right相遇进行判断如果目标值记录下标否则返回空
代码
class Solution {
public:vectorint searchRange(vectorint nums, int target) {if(nums.size() 0) return {-1,-1};int left 0,right nums.size()-1,mid;vectorint ret {-1,-1};while(leftright){mid (leftright)/2;if(nums[mid]target) right mid;else left mid1;}if(nums[left]target) ret[0] left;left 0,right nums.size()-1;while(leftright){mid (leftright)/2 1;if(nums[mid]target) right mid-1;else left mid;}if(nums[right]target) ret[1] right;return ret;}
};
3.x的平⽅根
难度等级⭐⭐⭐
题目链接69. x 的平方根 - 力扣LeetCode
题目描述 给你一个非负整数 x 计算并返回 x 的 算术平方根 。 由于返回类型是整数结果只保留 整数部分 小数部分将被 舍去 。 注意不允许使用任何内置指数函数和算符例如 pow(x, 0.5) 或者 x ** 0.5 。 示例 1 输入x 4
输出2示例 2 输入x 8
输出2
解释8 的算术平方根是 2.82842..., 由于返回类型是整数小数部分将被舍去。 算法思路
找一个数的平方根暴力枚举的思路是在小于该数的数组中从第一个元素开始判断当前元素的平方是否为目标元素。
用二分算法进行优化 在小于该数的数组中从中间元素开始判断之后更新成左右区间的中点继续判断。
在这道题中并不需要真的建立一个数组将left、right、mid就直接是对应的值
代码
class Solution {
public:int mySqrt(int x) {if(x0) return 0;if(x1) return 1;long long left 1,right x-1,mid;while(leftright){mid (leftright)/2 1;if(mid*mid (long long)x) right mid-1;else left mid;}return right;}
};
4.⼭峰数组的峰顶
难度等级⭐⭐⭐⭐
题目链接852. 山脉数组的峰顶索引 - 力扣LeetCode
题目描述 给定一个长度为 n 的整数 山脉 数组 arr 其中的值递增到一个 峰值元素 然后递减。 返回峰值元素的下标。 你必须设计并实现时间复杂度为 O(log(n)) 的解决方案。 示例 1 输入arr [0,1,0]
输出1示例 2 输入arr [0,2,1,0]
输出1示例 3 输入arr [0,10,5,2]
输出1 算法思路
这道题的暴力枚举思路很好想从头遍历数组与后一个元素进行判断如果大于后一个元素说明当前位置就是峰顶。
但是题目要求时间复杂度为O(logn) 说明指引我们用二分算法思想解决
但是这道题并不是一个有序数组我们也不能将其变成有序数组改变了峰顶的下标那么还能用二分进行解决吗
✅当然可以实际上二分算法并不局限于有序数组在无序数组中只要该数组具有二段性就依然可以使用二分进行解决 我们可以把数组看成两个区间其中6是我们的峰顶而寻找峰顶的问题就转化成了寻找连续区间a的右端点如此以来就可以用二分进行解决了。
算法流程
①定义left、right、mid由于寻找的是区间右端点根据极端情况判断mid应该等于left、right的右中点
②判断mid元素 a.左元素说明一定在b区间则right指向mid前一个位置更新mid b.右元素说明在a区间此时可能是峰顶left指向mid保存当前位置更新mid
③此时left、right相遇处即为峰顶
代码
class Solution {
public:int peakIndexInMountainArray(vectorint arr) {int left0,rightarr.size()-1,mid;while(leftright){mid (leftright)/2 1;if(arr[mid]arr[mid-1]) left mid;else right mid-1;}return left;}
};
5.点名 难度等级⭐⭐⭐
题目链接LCR 173. 点名 - 力扣LeetCode
题目描述 某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组 records。假定仅有一位同学缺席请返回他的学号。 示例 1: 输入: records [0,1,2,3,5]
输出: 4示例 2: 输入: records [0, 1, 2, 3, 4, 5, 6, 8]
输出: 7算法思路
这道题目是让我们寻找连续数组中缺失的元素解决方法其实有很多可以遍历数组也可以用哈希表解决但是这道题最快的方法还是二分查找 同样可以将数组看成ab两个区间而题目最终是让我们寻找区间a的右端点与上一道题目类似最终我们需要返回的是 区间a的右端点 的下一个下标。
代码
class Solution {
public:int takeAttendance(vectorint r) {if(r[0]!0) return 0;int left 0,right r.size()-1,mid;while(leftright){mid (leftright)/2 1;if(r[mid]mid) rightmid-1;else leftmid;}return left1;}
};
三、总结
二分算法是一种经典且高效的查询方法核心在于通过不断将查找范围缩小为一半从而大幅降低查找的时间复杂度从 O(n)优化为 O(logn)。要注意的是算法在实际应用中有几个关键细节如左右临界的处理、中点的选择以及避免死循环的循环条件设计。
我通过多个具体例题我们可以体会到二分算法的灵活性和强大之处其不仅适用于有序数组还可在满足一定性质的无序场景中巧妙运用。 以上就是【优选算法篇·第三章二分算法】的全部内容欢迎指正~
码文不易还请多多关注支持这是我持续创作的最大动力
