【刷题】 二分查找进阶
1 前言
二分查找的算法思想是很好理解的。朴素二分很容易，但一般常使用左端点查找与右端点查找来解决问题。 模版：
int left = 0 , right = nums.size() - 1;
while(left < right)
{
int mid = left + (right - left) / 2;
//int mid = left + (right - left + 1) / 2;
if( // 判断条件 )
{
left = mid + 1;
//left = mid
}
else
{
right = mid;
// right = mid - 1
}
}
return left;
//return right ;while（）循环条件是left < right!- 注意对应关系。right里有
-1那么对应的求中值就要有+1。把握这个规律，就不会弄乱了
下面来看几道例题，强化训练二分查找的算法思路！通过这些题的训练，就可以很熟悉二分查找算法的思想，以后遇到问题就多了一种解决手段！！！
Leetcode 852. 山脉数组的峰顶索引
题目描述
首先我们要理解什么是山峰数组，根据题目的描述，山峰数组就是先升再下降的数组。我们要在其中寻找峰值的索引。这个问题看起来看还是挺简单的
算法思路
首先我们要判断该数组是否存在二段性？？？ 当然有了！
- 以峰值为分割，左边都是
nums[n] < nums[n + 1]右边都是nums[n] > nums[n + 1]
通过这个二段性我们可以来进行二分查找：
- 如果中值落在左边，那么left 应该 移动到 mid + 1(因为
nums[n] < nums[n + 1]，mid对应的值一定不是峰值) - 如果中值落在右边，那么right 应该 移动到 mid(因为
nums[n] > nums[n + 1]，mid对应的值有可能是峰值)
有了思路，代码很简单就可以写出来，直接套用模版。
class Solution {
public:
int peakIndexInMountainArray(vector<int>& arr) {
int mid = 0;
int left = 0 , right = arr.size() - 1 ;
while( left < right )
{
mid = left + (right - left + 1) / 2;
if(arr[mid] > arr[mid - 1] && arr[mid] > arr[mid + 1])
{
return mid;
}
if(arr[mid] > arr[mid - 1])
{
left = mid;
}
else
{
right = mid - 1;
}
}
return mid;
}
};提交：过啦！！！！
Leetcode 162. 寻找峰值
家人们！！！跟上节奏：162. 寻找峰值
题目描述
这道题是上面求峰值索引的变形。这道题具有多个封值（换句话说数组是无序的），那么我们要在无序的数组寻找一个峰值。
算法思路
首先我们来看可不可以判断出来数组的二段性。和求峰值索引一样：
- 以其中一个峰值为分割，左边一部分是
nums[n] < nums[n + 1]右边一部分是nums[n] > nums[n + 1]
那么根据这个二段性也就是可以写出算法逻辑了：
- 如果中值落在左边，那么left 应该 移动到 mid + 1(因为
nums[n] < nums[n + 1]，右边一定存在一个峰值，mid对应的值一定不是峰值) - 如果中值落在右边，那么right 应该 移动到 mid(因为
nums[n] > nums[n + 1]，左边一定存在一个峰值，mid对应的值有可能是峰值)
有了思路，直接套用模版秒了！！！
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;
}
};提交 过啦！！！
Leetcode 153. 寻找旋转排序数组中的最小值
上链接！！！153. 寻找旋转排序数组中的最小值
题目描述
根据题目描述啊，是很好理解的，就是将一个有序的数组进行移动，使其旋转，形成一个先增长然后断崖后再增长的数组，我们要找到其中的最小值
算法思路
这个题的暴力算法很简单（我们不考虑），首先也是来分析二段性。这个二段性如何进行分析呢？？？
- 以其中 数组末位值为分割，由于旋转的特性，左边一部分是
大于末位值右边一部分是小于等于末位值
然后根据二段性进行算法分析：
- 如果中值落在左边，那么left 应该 移动到 mid + 1(左边一定不存在最小值，mid 对应的值一定不是最小值)
- 如果中值落在右边，那么right 应该 移动到 mid(右边一定不存在一个峰值，mid对应的值有可能是最小值)
根据算法逻辑，直接秒杀：
class Solution {
public:
int findMin(vector<int>& nums) {
//分析二段性质
//左边都大于 末位数字 右边都 小于等于 末尾数字
int left = 0;
int right = nums.size() - 1;
while(left < right)
{
int mid = left +(right - left) / 2;
//说明mid 在最小值 左边
if(nums[mid] > nums[nums.size() - 1])
{
left = mid + 1;
}
else
{
right = mid;
}
}
return nums[left];
}
};提交：过啦！！！
Leetcode LCR 173. 点名
最后一道：LCR 173. 点名！！！
题目描述
题目非常简单奥，就是寻找断点。（有坑哦）
算法思路
暴力算法有很多种：遍历，位运算，数学公式。我们来用更快速的二分查找算法 首先来分析二段性，这个其实不太好想
- 以其中断点为分割，左边一部分是
数组值与下标相等，右边一部分是数组值与下标不相等
根据这个二段性我们就可以来进行算法分析：
- 如果中值落在左边，那么left 应该 移动到 mid + 1(左边一定不存在断点，mid 对应的值一定不是断点)
- 如果中值落在右边，那么right 应该 移动到 mid(mid对应的值有可能是断点)
- 注意如果最后left到了最右边，那么缺少的是最后一名同学，要进行一个判断
根据这个算法逻辑，我们书写代码：
class Solution {
public:
int takeAttendance(vector<int>& nums) {
//寻找二段性
//左边下标对应 右边下标不对应
int left = 0 ;
int right = nums.size() - 1;
while(left < right)
{
int mid = left + (right - left ) / 2;
//
if(nums[mid] == mid)
{
left = mid + 1;
}
else
{
right = mid;
}
}
//left到了最右边,缺少的是最后一名同学，要进行一个判断
return nums[left] == left ? nums.size() : left ;
}
};提交过啦！！！
Thanks♪(･ω･)ﾉ谢谢阅读！！！
下一篇文章见
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2024-04-20，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录