【优选算法】Binary-Blade：二分查找的算法刃（下）
文章目录
- 1.山脉数组的峰顶索引
- 2.寻找峰值
- 3.寻找旋转排序数组中的最小值
- 4.点名
- 希望读者们多多三连支持
- 小编会继续更新
- 你们的鼓励就是我前进的动力！
本篇接上一篇二分查找，主要通过部分题目熟悉二分查找的进阶使用，重点强调二段性，找到两个区间不同的地方在哪，多画图划分界限
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;
}
};
希望读者们多多三连支持
小编会继续更新
你们的鼓励就是我前进的动力！
