【LeetCode 算法专题突破】---二分查找（⭐⭐⭐）

前言

我在算法题目的海洋中畅游已久，也曾在算法竞赛中荣获佳绩。然而，我发现自己对于算法的学习，还缺乏一个系统性的总结和归类。尽管我已经涉猎过不少算法类型，但心中仍旧觉得有所欠缺，未能形成完整的算法体系。

因此，我决定踏上这次算法之旅，对常见的算法进行一次全面的梳理与归类。我希望通过这个过程，能够更深入地理解每个经典算法类型的核心知识，加强我的算法能力，并完善自己的算法体系。

同时，我也希望能够将这次学习的成果与你分享，希望对你也有所帮助。让我们一同在算法的世界里探索、成长，共同迎接未来的挑战吧！

1.经典的不能在经典的二分查找（难度⭐）

Leetcode链接：704. 二分查找

1.1题目描述：

这是一道非常典型的二分查找算法题目,可以说所有要学习二分查找算法的人都必须掌握这道题。题目要求很简单,就是在一个有序数组中查找目标值target。这道题是二分查找算法的入门题和模版题,没有掌握这道题就无法开始学习更复杂的二分查找算法题目。所以这道题对于二分查找算法的理解和掌握非常关键和必要。

1.2代码：

class Solution {
public:int search(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1;int mid;while(left <= right){mid = (left + right)/2;if(nums[mid]>target){right = mid - 1;}else if(nums[mid]<target){left = mid + 1;}else{return mid;}}return -1;}
};

通过这道二分查找的典型题,我对二分查找算法的理解更进一步:

我对二分查找的区间划分有了更深的理解:

当mid位置的值小于target时,证明左区间[left, mid-1]都不可能存在target,所以左区间变为[mid+1, right]。
当mid位置的值大于target时,证明右区间[mid+1, right]都不可能存在target,所以右区间变为[left, mid-1]。
当mid位置的值等于target时,就找到了目标值。

我理解到二分查找的本质就是通过比较中间mid值与target的值,可以排除一半的搜索区间,使搜索范围越来越小,直到找到target。

通过这道题我对二分查找算法模板有了更加熟练的掌握,可以应用到其他二分查找题目中去。

2.在排序数组中查找元素的第一个和最后一个位置（难度⭐⭐）

Leetcode链接：34. 在排序数组中查找元素的第一个和最后一个位置

2.1题目描述：

2.2代码：

class Solution {
public:vector<int> searchRange(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1, begin = -1, end = -1, mid;//找到区间左边界while(left<=right){mid = (left + right)/2;if(nums[mid] > target){right = mid - 1;}else if(nums[mid] < target){left = mid + 1;}else{begin = mid;right--;//right区间左移，使得mid左移，直到到达左区间边界，此时right正好和left重合}}left = 0, right = nums.size() - 1;//找到区间有边界while(left<=right){mid = (left + right)/2;if(nums[mid] > target){right = mid - 1;}else if(nums[mid] < target){left = mid + 1;}else{end = mid;left++;//left区间右移，使得mid右移，直到到达又区间边界，此时left正好和right重合}}return {begin,end};}
};

这道题的大思路和上面的题并没有太大区别，只是为了找到左右区间，需要两次二分查找

具体来说,在求左右区间边界时,处理mid==target的情况需要进行特别考虑:

求左区间边界时,需要在记录begin索引后,继续将right索引左移,使得mid向左逼近,直到不等于target时才能锁定左区间边界。
求右区间边界时,需要在记录end索引后,继续将left索引右移,使得mid向右逼近,直到不等于target时才能锁定右区间边界。

这种细微的逻辑调整体现了二分查找的灵活性,在保持模板框架不变的情况下,通过简单逻辑修改就可应对新的问题。

3. 有效的完全平方数（难度⭐）

Leetcode链接：367. 有效的完全平方数

3.1题目描述：

撇开具体问题不讨论，假设需要找到完全平方数，你可能会采用这样的方法：将原数进行二分，然后将得到的中间值平方，观察是否等于目标值。如果相等，那么找到了完全平方数；如果不等，就可以根据大小关系缩小搜索范围，继续二分。为什么选择这种方式呢？因为这种方法的效率相对较高。既然如此，我们为何不考虑运用二分法来解决这类问题呢？

3.2代码：

class Solution {
public:bool isPerfectSquare(int num) {long long left = 0, right = num, mid = 0;long long s;while(left<=right){mid = (left + right)/2;s = mid * mid;if(s>num){right=mid-1;}else if(s<num){left=mid+1;}else{return true;}}return false;}
};

在这个解决方案中，我们并没有深入探讨具体的代码细节，只是简单地将二分算法应用于这个场景。然而，通过这个简单的经验，我们可以得出一个更加广泛的启示：如果今后遇到类似的问题，我们可以考虑运用二分法。

4.寻找峰值（难度⭐⭐）

二分熟练度up up up~

Leetcode链接：162. 寻找峰值

4.1题目描述：

在面对这个问题时，我们甚至没有提供目标值（target），而且输入序列并不保证是有序的。这是否意味着我们可以应用二分查找算法呢？
让我们尝试通过代码来展示这一思路，看看是否能够在这样的条件下成功运用二分查找的思想解决问题。

4.2代码：

class Solution {
public:int findPeakElement(vector<int>& nums) {int left = 0, right = nums.size() - 1, mid = 0;while(left<right){mid = (left + right)/2;if(nums[mid]>nums[mid + 1]){right = mid;}else{left = mid + 1;}}return right;}
};

初看之下，面对问题好像难以着手，但让我们仔细分析一下，看看能否找到解决方案。

题目要求在数组中找到任意一个峰值，那么我们可以考虑将数组分为两个区间：一个是递增区间，另一个是递减区间。峰值实际上是这两个区间的交界点。

假设我们随机选择一个点进行比较，如果它比右侧位置的值小，说明它在一个递增的区间；反之，如果它比右侧位置的值大，说明它在一个递减的区间。

基于这个性质，我们可以运用二分算法。当 nums[mid] < nums[mid+1] 时，表示在一个递增区间，峰值必定在 mid+1 及其之后的位置；而当 nums[mid] > nums[mid+1] 时，表示在一个递减区间，峰值可能在 mid 或其之前的位置（需要注意，峰值有可能就是在 mid 位置）。

因此，我们更新 right = mid，而不需要进行 -1 的操作。由于不需要 -1，当 left == right 时，如果已经找到峰值，我们应该如何退出循环呢？

这里可以进行特殊处理，或者将循环条件改成 left < right。在某些情况下，模板并不是固定不变的，我们可以根据实际情况进行调整。通过解决这道题，我们不仅学到了一些技巧，也积累了宝贵的经验。

5.寻找旋转排序数组中的最小值(难度⭐⭐)

Leetcode链接：153. 寻找旋转排序数组中的最小值

5.1题目描述：

这题的解题思路与前面一道问题相似，我们需要根据所给的条件找到一个可以进行比较的参照物或者说参照系。让我们来审视一下具体的代码。

5.2代码：

class Solution {
public:int findMin(vector<int>& nums) {int n = nums.size() - 1;int left = 0, right = n, mid = 0;while(left < right){mid = (left + right)/2;if(nums[mid] > nums[n]){left = mid + 1;}else if(nums[mid] < nums[n]){right = mid;}}return nums[left];}
};

考虑到题目给出的是一个经过旋转的升序数组，这使得数组不再是有序的，我们需要思考如何运用二分法来解决这一问题。

观察到，经过旋转的升序数组可以分为两个递增的区间，一个较大的区间和一个较小的区间。我们可以以区间的最大值作为参照物来进行分析。

以最右边的元素为例，它可能是小区间的最大值，也可能是大区间的最大值。如果它是大区间的最大值，这就意味着数组没有经过旋转，因此我们可以先忽略这种特殊情况（这是一个解题的小技巧，特殊情况可以后续再处理）。

题目要求找到最小的元素，即小区间的最小值。因此，我们需要找到小区间，并在其中找到最小元素。具体操作如下：

当 nums[mid] > nums[n] 时，表示中间位置 mid 处于大区间，因此将 left 调整为 mid + 1；
当 nums[mid] < nums[n] 时，表示中间位置 mid 处于小区间，因此将 right 调整为 mid。注意，这里不能减1，因为我们要找的值在小区间内，不能排除掉中间元素。
接着，考虑特殊情况，即当 nums[mid] < nums[n] 时，数组的最右元素 n 是大区间的最大值。如果我们让 right = mid，会导致最终循环结束时出现 left = right 的情况。为了避免这种情况，我们将循环的条件调整为 left < right。

这道题是二分法的一个变式，关键在于找到以何为参照系来确定区间的位置，一旦确定，后续的工作就变得相对容易。

6.点名（难度⭐）

Leetcode链接：LCR 173. 点名

6.1题目描述：

这道题我其实一开始也想不出来，选这道题的目的其实也是想说明，算法积累的重要性，见多识广，才能思路开阔，临危不乱。

6.2代码：

class Solution 
{
public:int takeAttendance(vector<int>& records) {int n = records.size() - 1;int left = 0, right = n, mid = 0;while(left < right){mid = (left + right)/2;if(records[mid] == mid){left = mid + 1;}else{right = mid;}}if (records[right] == right) {return right+1;}return right;}
};