目录
前言：
本文的主题是二分查找，通过三道题目讲解，一道是寻找峰值，一道是搜索旋转排序数组的最小值，一道是0 - n-1中缺失的数字。
链接分别为：
162. 寻找峰值 - 力扣（LeetCode）
153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）
LCR 173. 点名 - 力扣（LeetCode）
题目分为三个部分讲解，一是题目解析，二是算法原理，三是算法编写，那么，话不多说，直接进行主题咯。
寻找峰值
题目解析
题目是给了我们一个数组，这个数组并不像我们之前的数组一样具有明显的二段性，这个数组可以说是一个完全无序的数组，而我们要寻找的，是满足大于左右两值的数的索引，那么暴力解法简直就是不用经过大脑的，直接遍历数组即可，只要满足大于i - 1和 i + 1就可以了。
那么时间复杂度是显而易见的，直接就是O(N)了。
但是我们没有利用题目的条件，虽然是无序的，但是峰值的条件是大于左右两边，我们可以利用这个条件，使用二分查找。
算法原理
题目的隐含条件，左右两端都是负无穷的，数组可以有二段性，为：
我们随便定义一个位置，如果arr[i] > arr[i + 1]的话，那么在左区间一定是存在答案的，因为从num[-1]开始是负无穷，此时我们可以套用查找左端点的二分模板，对于右边的端点同理，如果arr[i] < arr[i + 1]，代表右边有答案，因为nums[n]也是负无穷的。
所以我们就可以直接进入到算法编写了。
算法编写
class Solution
{
public:
int findPeakElement(vector<int>& nums)
{
int left = 0, right = nums.size() - 1;
while(left < right)
{
int mid = left + (right - left + 1) / 2;
if(nums[mid] > nums[mid - 1]) left = mid;
else right = mid - 1;
}
return left;
}
};所以，不是非要有序的才会存在二段性，像这种完全无序的，也是会存在二段性的。
寻找旋转排序数组中的最小值
题目解析
题目看起来非常复杂，但是实际上非常简单，无非就是介绍如何旋转数组介绍的多了一点而已，题目给的条件有原来是一个升序排序的数组，并且每个元素都不相同，要让我们找到一个最小的值。
要找最小的值还不简单吗？直接一个for循环遍历就可以了。
但是题目还要求了使用logN的算法解决该问题。那就是典型的使用二分咯。
如果使用的是暴力就是O(N)了。
算法原理
二分查找算法的原理都是需要看是否存在二段性，如果存在二段性的话，我们就可以使用二分查找算法了。
注意，最开始的数组是有序的，所以我们可以这样分数组：
而我们要找的，不就是C这个点吗！如果mid的值大于了D，也就是在AB段，我们就应该让left = mid + 1，如果mid 的值 < D，也就是可能命中我们要的答案，就让right = mid就好了。
那么这里有一个疑问，如果我们使用的参照物是A呢？
算法编写
class Solution
{
public:
int findMin(vector<int>& nums)
{
int left = 0, right = nums.size() - 1;
int x = nums.size() - 1;
while(left < right)
{
int mid = left + (right - left) / 2;
if(nums[mid] < nums[x]) right = mid;
else left = mid + 1;
}
return nums[left];
}
};这是参照物为D的情况，如果参照物是A的话：
class Solution
{
public:
int findMin(vector<int>& nums)
{
int left = 0, right = nums.size() - 1;
int x = nums.size() - 1;
if(nums[0] < nums[x]) return nums[0];
while(left < right)
{
int mid = left + (right - left) / 2;
if(nums[mid] < nums[0]) right = mid;
else left = mid + 1;
}
return nums[left];
}
};如果参照物是A的情况，那么我们需要单独考虑数组是连续递增的情况，比如[1,2,3,4]，如果参照物是A，也就是1，那么任意的数都会大于1，此时，left会一直++到4，最后返回的恰好是最大的而非最小的，那么这种情况，也就代表了数组没有经过旋转，所以直接返回nums[0]即可。
寻找缺失的数字
题目解析
题目要求非常简单，要求返回缺失的那个数字就可以了。
那这个题目虽然是简单难度，可是就非常有说法了。
什么说法呢？这道题可以有很多很多的解法。
比如我们可以直接遍历数组，如果前一个不等于后一个加一，就代表缺少了。
比如我们可以直接使用数学中的等差求和公式，减去整个数组的和就可以了。
比如我们可以使用位运算，利用^的特点，数^本身就是0，最后留下一个没有异或自己的数，从而找到。
比如我们可以利用哈希映射，将所有的值全部映射到一个数组里面，判断哪个数组的元素为0，也就可以返回对应的值了。
但是但是，以上的所有方法，四种方法都是O(N)的，并且哈希映射的方法还新开了一个空间，空间复杂度还是O(N)。就实际上来说都是比较慢的，我们可以利用二分查找来优化。
算法原理
算法原理，一问就是哪里去找二段性？
缺失的数字的左边，数组的元素都是等于数组的下标的，而缺失的数字的右边，数组的元素的下标都是不等于数组的元素的。而我们要的值是右边的左端点，所以left = mid + 1，right = mid，算法一下就明了了。
算法编写
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 left == records[left] ? left + 1 : left;
}
};唯一需要注意的就是，如果数组是0 1 2 3 ，代表缺失的数字是4，所以此时不存在右边的区间，此时left和nums[left]相等的，所以需要left + 1。
二分查找的部分题目就先到这里了。
感谢阅读！
标签：二分,right,nums,mid,查找,算法,初识,数组,left From： https://blog.csdn.net/2301_79697943/article/details/143181125