【看海的算法日记✨优选篇✨】第三回：二分之妙，寻径中道

🎬 个人主页：谁在夜里看海.

📖 个人专栏：《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需要指向右区间的中点，而左区间（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.⼆分查找

难度等级：⭐⭐⭐

题目链接：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(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;}
};