【看海的算法日记✨优选篇✨】第三回：二分之妙，寻径中道
🎬 个人主页：谁在夜里看海.
⛰️ 一念既出，万山无阻
目录
📖一、算法思想
二分算法是一种经典的高效查询方法，它的核心思想是通过不断将查找范围缩小为一半，从而大大减少查找的时间复杂度。
例如，在一个有序数组中，我们要查找指定元素，最简单的方法是遍历数组，时间复杂度为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需要指向右区间的中点，而左区间（1，2，3）被排除了，所以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)的算法并不多见，因为高效率的同时，门槛也越高，我们常了解到的二分算法只能在有序数组中使用，如果数组无序，我们就不能保证目标元素在左或右区间，就不能一次排除一般的元素。
📚循环条件
循环条件是 left<right 还是 left<=right ? 其实就是考虑left、right相遇之后要不要进入循环
①：目标元素（不重复）
mid指针每次更新前都会进行一次判断，如果不是目标元素，则更新继续进入循环；当left、right相遇时，同样需要进行判断，如果还不是目标元素，则没有结果，这个判断和前面的判断一致，不需要特殊处理，所以循环条件是left<=right。
②：目标区间的端点
当left与right相遇后， 如果当前值不为目标值，那么更新left或right指针，会正常退出循环；如果当前值是目标值，那么left与right指针都会停留在当前位置，此时就进入了死循环。为了避免死循环，我们需要将循环条件设成left<right，并且在循环外部额外判断一次。
❓只能是有序数组吗
✅其实并不是，二分算法的巧妙就巧妙在，同样适用于一些无序的场景，后面会碰到具体例题。
📖二、具体运用
1.⼆分查找
难度等级：⭐⭐⭐
题目描述：
给定一个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(vector<int>& nums, int target) { int left = 0,right = nums.size()-1,mid = (left+right)/2; while(left<=right) { if(nums[mid]>target) right = mid-1; else if(nums[mid]<target) left = mid+1; mid = (left+right)/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]
算法思路
这道题目就是查找连续区间的端点的情况，查找左右端点需要分别进行。在查找时需要注意细节的处理：左右临界的选择、中点的选择 、循环条件（left<right）
算法流程
找区间左端点：
①：定义left、right、mid，mid指向left、right的左中点
②：判断mid元素
a.<目标值，right指向mid后一个位置，更新mid
b.>=目标值，left指向mid，更新mid
③：此时left、right相遇，进行判断，如果=目标值，记录下标；否则返回空
找区间右端点：
①：定义left、right、mid，mid指向left、right的右中点
②：判断mid元素
a.>目标值，left指向mid前一个位置，更新mid
b.<=目标值，right指向mid，更新mid
③：此时left、right相遇，进行判断，如果=目标值，记录下标；否则返回空
代码
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,mid; vector<int> ret = {-1,-1}; while(left<right) { mid = (left+right)/2; if(nums[mid]>=target) right = mid; else left = mid+1; } if(nums[left]==target) ret[0] = left; left = 0,right = nums.size()-1; while(left<right) { mid = (left+right)/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(x==0) return 0; if(x==1) return 1; long long left = 1,right = x-1,mid; while(left<right) { mid = (left+right)/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(vector<int>& arr) { int left=0,right=arr.size()-1,mid; while(left<right) { mid = (left+right)/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
算法思路
这道题目是让我们寻找连续数组中缺失的元素，解决方法其实有很多，可以遍历数组，也可以用哈希表解决，但是这道题最快的方法还是二分查找：
同样可以将数组看成a，b两个区间，而题目最终是让我们寻找区间a的右端点，与上一道题目类似，最终我们需要返回的是 区间a的右端点 的下一个下标。
代码
class Solution { public: int takeAttendance(vector<int>& r) { if(r[0]!=0) return 0; int left = 0,right = r.size()-1,mid; while(left<right) { mid = (left+right)/2 + 1; if(r[mid]>mid) right=mid-1; else left=mid; } return left+1; } };📖三、总结
二分算法是一种经典且高效的查询方法，核心在于通过不断将查找范围缩小为一半，从而大幅降低查找的时间复杂度，从 O(n)优化为 O(logn)。要注意的是，算法在实际应用中有几个关键细节，如左右临界的处理、中点的选择，以及避免死循环的循环条件设计。
我通过多个具体例题，我们可以体会到二分算法的灵活性和强大之处：其不仅适用于有序数组，还可在满足一定性质的无序场景中巧妙运用。
以上就是【优选算法篇·第三章：二分算法】的全部内容，欢迎指正~
码文不易，还请多多关注支持，这是我持续创作的最大动力！
