送给大家一句话：
你向神求助是因为相信神，神没有回应你是因为神相信你
ε≡٩(๑>₃<)۶ ε≡٩(๑>₃<)۶ ε≡٩(๑>₃<)۶ 一心向学
二分查找进阶
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]
通过这个二段性我们可以来进行二分查找：
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 ; } };
提交过啦！！！
