优选算法之二分查找（下）
目录
一、山脉数组的峰顶索引
1.题目链接：852. 山脉数组的峰顶索引
2.题目描述：
给定一个长度为
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提示：
3 <= arr.length <= 1050 <= arr[i] <= 106- 题目数据 保证
arr是一个山脉数组
3.解法一（暴力查找）
🌵算法思路：
峰顶的特点：比两侧的元素都要大。
因此，我们可以遍历数组内的每一个元素，找到某一个元素比两边的元素大即可。
🌵算法代码：
class Solution
{
public:
int peakIndexInMountainArray(vector<int>& arr)
{
int n = arr.size();
// 遍历数组内每⼀个元素，直到找到峰顶
for (int i = 1; i < n - 1; i++)
// 峰顶满⾜的条件
if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1])
return i;
// 为了处理 oj 需要控制所有路径都有返回值
return -1;
}
};4.解法二（二分查找）
🌵算法思路：
1. 分析峰顶位置的数据特点，以及⼭峰两旁的数据的特点：
- 峰顶数据特点： arr[i] > arr[i - 1] && arr[i] > arr[i + 1] ；
- 峰顶左边的数据特点： arr[i] > arr[i - 1] && arr[i] < arr[i + 1] ，也就是呈现上升趋势；
- 峰顶右边数据的特点： arr[i] < arr[i - 1] && arr[i] > arr[i + 1] ，也就是呈现下降趋势。
2. 因此，根据 mid 位置的信息，我们可以分为下面三种情况：
- 如果 mid 位置呈现上升趋势，说明我们接下来要在 [mid + 1, right] 区间继续搜索；
- 如果 mid 位置呈现下降趋势，说明我们接下来要在[left, mid - 1] 区间搜索；
- 如果 mid 位置就是山峰，直接返回结果。
🌵算法代码：
class Solution
{
public:
int peakIndexInMountainArray(vector<int>& arr)
{
int left = 1, right = arr.size() - 2;
while(left < right)
{
int mid = left + (right - left + 1) / 2;
if(arr[mid] > arr[mid - 1])
left = mid;
else
right = mid - 1;
}
return left;
}
};二、寻找峰值
1.题目链接：162. 寻找峰值
2.题目描述：
峰值元素是指其值严格大于左右相邻值的元素。
给你一个整数数组
nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。你可以假设
nums[-1] = nums[n] = -∞。你必须实现时间复杂度为
O(log n)的算法来解决此问题。示例 1：
输入：nums = [1,2,3,1] 输出：2 解释：3 是峰值元素，你的函数应该返回其索引 2。示例 2：
输入：nums = [1,2,1,3,5,6,4] 输出：1 或 5 解释：你的函数可以返回索引 1，其峰值元素为 2； 或者返回索引 5， 其峰值元素为 6。提示：
1 <= nums.length <= 1000-231 <= nums[i] <= 231 - 1- 对于所有有效的
i都有nums[i] != nums[i + 1]
3.解法（二分查找）
🌵算法思路：
寻找二段性：
任取⼀个点 i ，与下⼀个点 i + 1 ，会有如下两种情况：
- arr[i] > arr[i + 1] ：此时「左侧区域」一定会存在山峰（因为最左侧是负无穷），那么我们可以去左侧去寻找结果；
- arr[i] < arr[i + 1] ：此时「右侧区域」⼀定会存在山峰（因为最右侧是负无穷），那么我们可以去右侧去寻找结果。
当我们找到「二段性」的时候，就可以尝试用「二分查找」算法来解决问题。
🌵算法代码：
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;
}
};三、寻找旋转排序数组中的最小值
1.题目链接：153. 寻找旋转排序数组中的最小值
2.题目信息：
已知一个长度为
n的数组，预先按照升序排列，经由1到n次 旋转 后，得到输入数组。例如，原数组nums = [0,1,2,4,5,6,7]在变化后可能得到：
- 若旋转
4次，则可以得到[4,5,6,7,0,1,2]- 若旋转
7次，则可以得到[0,1,2,4,5,6,7]注意，数组
[a[0], a[1], a[2], ..., a[n-1]]旋转一次 的结果为数组[a[n-1], a[0], a[1], a[2], ..., a[n-2]]。给你一个元素值 互不相同 的数组
nums，它原来是一个升序排列的数组，并按上述情形进行了多次旋转。请你找出并返回数组中的 最小元素 。你必须设计一个时间复杂度为
O(log n)的算法解决此问题。示例 1：
输入：nums = [3,4,5,1,2] 输出：1 解释：原数组为 [1,2,3,4,5] ，旋转 3 次得到输入数组。示例 2：
输入：nums = [4,5,6,7,0,1,2] 输出：0 解释：原数组为 [0,1,2,4,5,6,7] ，旋转 3 次得到输入数组。示例 3：
输入：nums = [11,13,15,17] 输出：11 解释：原数组为 [11,13,15,17] ，旋转 4 次得到输入数组。提示：
n == nums.length1 <= n <= 5000-5000 <= nums[i] <= 5000nums中的所有整数 互不相同nums原来是一个升序排序的数组，并进行了1至n次旋转
3.解法一（暴力查找）
🌵算法思路：
- 遍历整个数组，从第一个元素开始逐个比较。
- 比较当前元素与下一个元素的大小，找到第一个出现下降的位置即为旋转点，即当前元素为最小值。
- 如果遍历完数组没有找到下降的位置，则旋转点为数组的第一个元素。
🌵算法代码：
class Solution
{
public:
int findMin(vector<int>& nums)
{
int n = nums.size();
for(int i = 0; i < n - 1; i++)
{
if(nums[i] > nums[i + 1])
return nums[i + 1];
}
return nums[0];
}
};4.解法二（二分查找）
🌵算法思路：
题目中的数组规则如下图所示：
其中 C 点就是我们要求的点。
二分的本质：找到一个判断标准，使得查找区间能够一分为二。
通过图像我们可以发现， [A，B] 区间内的点都是严格大于 D 点的值的， C 点的值是严格小于 D 点的值的。但是当 [C，D] 区间只有一个元素的时候， C 点的值是可能等于 D 点的值的。
因此，初始化左右两个指针 left ， right ：
然后根据 mid 的落点，我们可以这样划分下一次查询的区间：
- 当 mid 在 [A，B] 区间的时候，也就是 mid 位置的值严格大于 D 点的值，下一次查询区间在 [mid + 1，right] 上；
- 当 mid 在 [C，D] 区间的时候，也就是 mid 位置的值严格小于等于 D 点的值，下次查询区间在 [left，mid] 上。
当区间长度变成 1 的时候，就是我们要找的结果。
🌵算法代码：
class Solution
{
public:
int findMin(vector<int>& nums)
{
int left = 0, right = nums.size() - 1;
int end = nums[right];
while (left < right)
{
int mid = left + (right - left) / 2;
if (nums[mid] > end)
left = mid + 1;
else
right = mid;
}
return nums[left];
}
};四、点名
1.题目链接：LCR 173. 点名
2.题目信息：
某班级 n 位同学的学号为 0 ~ n-1。点名结果记录于升序数组
records。假定仅有一位同学缺席，请返回他的学号。示例 1:
输入: records = [0,1,2,3,5] 输出: 4示例 2:
输入: records = [0, 1, 2, 3, 4, 5, 6, 8] 输出: 7提示：
1 <= records.length <= 10000
3.解法（二分查找）
🌵算法思路：
关于这道题中，时间复杂度为 O(N) 的解法有很多种，例如：利用哈希、位运算、数学方法（高斯求和）等，而且也是比较好想的，这里就不再赘述了。
本题我们只用一个最优的二分法，来解决这个问题。
在这个升序的数组中，我们发现：
- 在第⼀个缺失位置的左边，数组内的元素都是与数组的下标相等的；
- 在第⼀个缺失位置的右边，数组内的元素与数组下标是不相等的。
因此，我们可以利用这个「二段性」，来使用「二分查找」算法。
🌵算法代码：
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[right] == right ? right + 1 : right;
}
};原文地址：https://blog.csdn.net/weixin_65931202/article/details/140613539
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！