【优选算法】Binary-Blade：二分查找的算法刃（下）

本篇接上一篇二分查找，主要通过部分题目熟悉二分查找的进阶使用，重点强调二段性，找到两个区间不同的地方在哪，多画图划分界限

1.山脉数组的峰顶索引

✏️题目描述：

✏️示例：

传送门：山脉数组的峰顶索引

题解:
💻第一步：

首先确定二段性，把顶峰放到左区间还是右区间取决于你自己，会根据取法不同而导致代码不同，但是都能求出顶峰索引，这里我们放到左区间

💻第二步：

按照我们的划分方式，要确保左边区间不会越过分界，右边区间同理，就要用mid和mid-1这种划分方式。如果在左区间，那么mid会有等于峰顶索引，即left = mid；如果在右区间，mid及其后面的值都不可能是峰顶索引，即right = mid - 1

💻细节问题:

对于二分查找进阶模版，如果在if语句的函数体里有减法操作时，那么计算mid的公式就要+1

💻代码实现:

#include <iostream>
#include <vector>
using namespace std;class Solution 
{
public:int peakIndexInMountainArray(vector<int>& arr) {int left = 0, right = arr.size() - 1;while (left < right){int mid = left + (right - left + 1) / 2;if (arr[mid] > arr[mid - 1]){left = mid;}else{right = mid - 1;}}return right;}
};

2.寻找峰值

✏️题目描述：

✏️示例：

传送门：寻找峰值

题解:
💻第一步：

首先确定二段性，可以分为在上坡或者下坡，其实这道题和山脉数组的峰顶索引是一样的，这里我们顶峰放在右区间里

💻第二步：

按照我们的划分方式，要确保右边区间不会越过分界，左边区间同理，就要用mid和mid+1这种划分方式。如果在右区间，那么mid会有等于峰顶索引，即right = mid；如果在左区间，mid及其前面的值都不可能是峰顶索引，即left = mid + 1

💻代码实现:

#include <iostream>
#include <vector>
using namespace std;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]){left = mid + 1;}else{right = mid;}}return left;}
};

3.寻找旋转排序数组中的最小值

✏️题目描述：

✏️示例：

传送门：寻找旋转排序数组中的最小值

题解:
💻第一步：

根据画图，似乎不太好确认二段性，但我们可以发现以D点为分界点，左区间的数（A到B）都大于D，右区间的数（C到D）都小于D，那么由此就能确定二段性，不断向中寻找最小的数

💻第二步：

如果在右区间，那么mid会有等于最小值，即right = mid；如果在左区间，mid及其前面的值都不可能是最小值，即left = mid + 1

💻代码实现:

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

4.点名

✏️题目描述：

✏️示例：

传送门：点名

题解:
💻第一步：

在连续数组的前提下，缺失数字的位置开始下标与实际值不同，很明显二段性立马就出来了

💻第二步：

如果在右区间，那么mid会有等于缺失值的实际位置索引，即right = mid；如果在左区间，mid及其前面的值都不可能是缺失值的实际位置索引，即left = mid + 1

💻代码实现:

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

---

希望读者们多多三连支持

小编会继续更新

你们的鼓励就是我前进的动力！