二分查找算法

题目1——704. 二分查找 - 力扣（LeetCode）

1.1.暴力解法

1.2.二分查找算法

1.3.朴素的二分查找算法模板

题目2——34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

2.1.暴力解法

2.2.二分查找算法（查找区间左端点）

2.2.1.数组划分成两部分

2.2.2.循环条件

2.2.3.求middle的操作

2.2.4.查找区间左端点的模板

2.3.二分查找算法（查找区间右端点）

2.3.1.数组划分成两部分

2.3.2.循环条件

2.3.3.求middle的操作

2.3.4.查找区间右端点的模板

2.4.题解

题目3——69. x 的平方根 - 力扣（LeetCode）

3.1.暴力解法

3.2.二分查找算法

3.2.1.找数组二段性

3.2.2.left和right的初始位置应该在哪里呢？

题目4——35. 搜索插入位置 - 力扣（LeetCode）

4.1.二分查找

4.1.1.找数组二段性

4.1.2.left和right的初始位置应该在哪里？

题目5——852. 山脉数组的峰顶索引 - 力扣（LeetCode）

5.1.暴力解法

5.2.二分查找算法

5.2.1.找数组二段性

题目6——162. 寻找峰值 - 力扣（LeetCode）

6.1.暴力解法

6.2.二分查找算法

6.2.1.找数组二段性

题目7——153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

7.1.暴力解法

7.2.二分查找算法

题目8——LCR 173. 点名 - 力扣（LeetCode）

8.1.暴力解法1——直接遍历

8.2.二分查找算法

8.2.1.数组的划分

8.2.2.left和right的初始位置应该在哪里？

二分查找算法

二分查找算法是这些基础算法里面最恶心的，细节最多的，最容易写出死循环的算法，而且特别难发现。

但是如果我们真正掌握了二分查找算法，我们就不太可能用错它了。

我们经常说二分查找算法是需要在数组有序的情况下使用，但事实上，二分查找比你想象中NB，它在数组无序，但是有一些有规律的情况下，还是可以使用二分查找算法的！！！

而且，大家也知道二分查找是有模板的，但是我们不应该死记硬背，而应该理解后再加以背诵。

我们这里会讲3个模板

1.朴素的二分模板——>下面的第1题
2.查找左边界的二分模板——下面的第2道题目
3.查找右边界的二分模板——下面的第2道题目

掌握了上面3个模板，就能解决99.99%的二分问题

第一个模板是最优选
后面两个基本就是万能模板的，但是细节多

题目1——704. 二分查找 - 力扣（LeetCode）

这道题目是特别简单的！！！

1.1.暴力解法

我们先写暴力解法，只有这样子，我们才能理解二分查找的本质

class Solution {
public:int search(vector<int>& nums, int target) {int ret=-1;for(int n=0;n<nums.size();n++){if(nums[n]==target){ret=n;}}return ret;}
};

1.2.二分查找算法

我们看到上面的暴力解法了吗？它每次都只能排除一个数，时间复杂度应该是O(N)；

但是这个暴力解法没有使用到数组是有序的这个特点！！

看到数组有序了吗！！！这个特别重要

二分查找（Binary Searc）算法，也叫折半查找算法。二分查找针对的是一个有序的数据集合，每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。
算法复杂度为O(logn)。
在数组是升序的情况下，如果查找值比中间位置的元素小，则从数组的左边继续查找，如果查找值比中间位置的元素大，则从数组的右边继续查找。

上面是我搜到的二分查找算法。但是事实上二分查找不仅仅只适用与一个有序的数组，只要数组满足"二段性”，那就可以使用二分查找算法。

什么时候能用二分查找算法？

我们在执行的时候，能通过特定条件把数组分成两半，然后通过条件舍去其中一半，一直这样往复下去。这个时候就能使用二分查找算法

二分查找有2个细节问题：

1.什么时候循环结束？

当left<right的时候，这个肯定不能结束。
left==right的时候，middle==left==right，这个位置的数还是要判断的
当left>right的时候，循环才能结束。

2.时间复杂度

O(logN)

我们可能写出下面这个代码，当然他没有大错误

class Solution {
public:int search(vector<int>& nums, int target) {int res=-1;int left=0,right=nums.size()-1;int middle;while(left<=right){middle=(right+left)/2;if(nums[middle]>target){right=middle-1;}else if(nums[middle]<target){left=middle+1;}else{res=middle;break;}}return res;}
};

可是大家仔细看这里

当我们的数据量很大的时候，这个right+left的时候，是会溢出的。所以我们需要修改一下，不要使用right+left。下面这个就可以

class Solution {
public:int search(vector<int>& nums, int target) {int res=-1;int left=0,right=nums.size()-1;int middle;while(left<=right){middle=left+(right-left)/2;if(nums[middle]>target){right=middle-1;}else if(nums[middle]<target){left=middle+1;}else{res=middle;break;}}return res;}
};

1.3.朴素的二分查找算法模板

while (left <= right)//这个判断条件一定要注意
{middle = left + (right - left) / 2;//这个注意防溢出if (.....){right = middle - 1;}else if (.....){left = middle + 1;}else{......}
}

此外我们得知道，在朴素版本里面

 middle = left + (right - left) / 2;middle = left + (right - left + 1) / 2;

这两种写法在当前朴素版本二分查找算法里面是等价的。唯一的区别是数据量是偶数的时候

当数据量是奇数的时候，[0,4]中间，4/2和5/2都是2
当数据量是偶数的时候，[0,3]，3/2=1，4/2=2，得到的下标不一样。

其实取两个元素里面的哪一个元素，在朴素版本的二分查找是没干系的，不影响。

题目2——34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

来审一下题目。

什么叫非递减顺序排列？

就是数组元素的大小是按照下面这种趋势排列的

要么变大，要么相等。

假设我们有以下数组和目标值：

nums = [1, 2, 2, 2, 3, 4, 5]
target = 2

在这个数组中，目标值 2 出现了三次，分别在索引 1, 2, 和 3。根据题目的要求，我们需要找到 2 的起始位置和结束位置。

起始位置是第一个 2 出现的索引，即 1。
结束位置是最后一个 2 出现的索引，即 3。

因此，对于给定的数组和目标值，函数应该返回 [1, 3]。

2.1.暴力解法

这个暴力解法太简单了，直接一个for循环找到这个target，然后我们再使用一个for循环，看看这个target的末尾在哪里？话不多说，看代码

class Solution {
public:// 定义一个函数，接收一个整数数组和一个目标值，返回一个包含起始和结束索引的vectorstd::vector<int> searchRange(std::vector<int>& nums, int target) {// 如果数组为空，则返回{-1, -1}，表示目标值不存在if(nums.size()==0) {return {-1,-1};}std::vector<int> res; // 初始化结果vector，用于存储起始和结束索引// 遍历数组，寻找目标值for(int i=0; i<nums.size();) {// 如果当前元素等于目标值if(nums[i]==target) {int n=i; // 初始化一个变量n，用于记录连续目标值的结束位置// 在不越界且当前元素等于目标值的情况下，继续向后遍历while(n<nums.size() && nums[n]==target) {n++;}// 将起始索引和结束索引（n-1，因为n已经自增了1）添加到结果vector中res.push_back(i);res.push_back(n-1);// 更新i的值，使其跳过当前连续的目标值序列，继续向后搜索i=n;}// 如果当前元素不等于目标值，则i自增，继续向后遍历else {i++;}}// 如果结果vector的大小为0，说明没有找到目标值，返回{-1, -1}if(res.size()==0) {return {-1,-1};}// 如果找到了目标值，则返回包含起始和结束索引的结果vectorelse {return res;}}
};

2.2.二分查找算法（查找区间左端点）

但是上面这个暴力解法没有利用数组有序的特点，所以我们就可以使用二分查找。

我们首先使用一下朴素二分查找算法来解决这个问题

但是我们发现，我们只能找到这个target，但是我们不能直接找到这个位置是不是target序列的最开始位置还是最后面的位置。

如果要找到这个 target序列的最开始位置和最后面的位置，我们就得另外使用for循环来查找，这样子时间复杂度就会上升。

所以，我们可以改进一下这个朴素版本的二分查找算法

2.2.1.数组划分成两部分

1.查找区间的左端点

如果我们要找左端点，我们可以将数组分成两部分，一部分是左端点左边的那些元素，另外一半是左端点右边那些数（包括左端点）

如下图

左边区域的特点就是小于target，右边区域的特点是大于等于target的。这就具有二段性。我们就可以使用二分查找算法。

这样子我们就能优化我们的朴素版本的二分查找算法

当nums[middle]<target的时候，

我们就能发现middle是在左边这个区间的，而我们寻找的左端点可不是在左边这个区域。所以这个时候把left更新成middle+1即可
（因为middle落在的那个点是不符合要求的，要舍去）

当nums[middle]>=target的时候，

我们将>和=放到一起来讨论的原因就是当nums[middle]=target的时候，这个位置并不一定是左端点
我们就能发现middle是在右边这个区间的，而我们寻找的左端点就在右边这个区域。
这个时候，我们要怎么移动啊？
我们直接让right更新成middle即可（为啥更新成middle-1?因为这个是middle可能刚好位于区间左端点）

接下来就是二分查找最恶心的地方了，就是里面的一些细节

循环条件
求middle的操作

2.2.2.循环条件

什么时候我们执行二分查找操作？

一般就是下面这两种

left<=right的时候
left<right的时候

这个时候我们一定要使用第2种

为什么呢？

我们分3种情况讨论一下：

第一种情况是序列里面有结果
第二种情况就是序列里面全都是大于target的
第三种情况就是序列里面全都是小于target的

因为这3种情况就是符合这道题的所有情况了

情况一：序列里面有结果

首先序列会被分成两份

如下图

左边区域的特点就是小于target，右边区域的特点是大于等于target的。

我们知道二分查找的过程中，left一定会在左端点的左边，也就是左边区域，而right一定会在右边这个区域；
left永远都是想跳出左边的这个区域的（因为left=middle+1）
所以当left==right的时候，这个点就是左端点。

所以left==right的时候就是最终的结果，无需判断。

没有必要再进去循环里面进行判断。

情况二：序列里面全都是大于target的

这个时候，我们发现right会疯狂往左边移动，而left是永远不会动的，所以直到right移动到与left相等时，这个时候只需再判断这个点是不是target就行了。没有必要再进去循环里面进行判断。

情况三：序列里面全都是小于target的

这个时候，right是根本不会动的，而left会疯狂往右边移动。所以当left==right的时候，再判断这个点是不是target就好了。没有必要再进去循环里面进行判断。

上面三点都是总结出了一句话，当left==right的时候，只需要将nums[middle]和target进行判断即可。 没有必要再进去循环里面进行判断。

所以我们的循环条件就不能出现right==left的情况，也就是就是不能写left<=right

要将right==left的情况，放到循环外面来处理！

如果说我们在right==left的情况还让它进去循环里面进行判断，就会产生死循环！！！！！！

为什么这么说？我们看下面

我们如果在循环里面判断，就会需要求middle，这个时候middle就不变化，而nums[middle]是符合nums[middle]>=target的，所以会执行right=middle；这个right就不会动，然后又进入下一次判断，就这样子会产生死循环。

另外两种情况也是类似的，我就不提了。

总结起来就下面这个图

2.2.3.求middle的操作

我们之前写过两种形式

middle=left+(right-left)/2;
middle=left+(right-left+1)/2;

这两个的区别无非就是数组元素个数是偶数的时候

第一种：middle = left + (right - left) / 2;

这是最常用的计算方式。它总是将区间 [left, right] 划分为两个尽可能相等的部分，并向下取整。因此，middle 会偏向左侧。

区间划分：这种方式通常用于查找在[left, right]区间内的元素，并且更新区间时，通常会是[left, middle-1]和[middle+1, right]。
例子：
如果 left = 0，right = 3，那么 middle = 0 + (3 - 0) / 2 = 1。
区间被划分为 [0, 1-1] 和 [1+1, 3]，即 [0, 0] 和 [2, 3]。

第二种：middle = left + (right - left + 1) / 2;

这种方式会将区间 [left, right] 划分为两部分，但 middle 会向上取整。因此，middle 会偏向右侧。

区间划分：这种方式有时用于特定的二分查找变种，比如当需要在某些特定条件下偏向右侧时。更新区间时，可能会是[left, middle-1]和[middle, right]。
例子：
如果 left = 0，right = 3，那么 middle = 0 + (3 - 0 + 1) / 2 = 2。
区间被划分为 [0, 2-1] 和 [2, 3]，即 [0, 1] 和 [2, 3]。

那么我们现在来看看，使用哪一个好呢？

先看看middle = left + (right - left + 1) / 2;

假设只有两个不同的元素，如下图

这个时候我们使用middle = left + (right - left + 1) / 2;求得的middle就位于靠右边那个元素了

这个时候，

假如说nums[middle]<target，按照我们上面的设定，那么left=middle+1，left>right，循环结束，这是没有问题的
假如说nums[middle]>=target，按照我们上面的设定，那么right=middle，right不动，就陷入了死循环

这就说明middle = left + (right - left + 1) / 2;是有大缺陷的。

我们再看看middle = left + (right - left) / 2;

假设只有两个不同的元素，如下图

这个时候我们使用middle = left + (right - left ) / 2;求得的middle就位于靠左边那个元素了

这个时候，

假如说nums[middle]<target，按照我们上面的设定，那么left=middle+1，然后left==right，循环结束，这是没有问题的
假如说nums[middle]>=target，按照我们上面的设定，那么right=middle，right就会==left，也是没有问题的

所以我们只会使用middle = left + (right - left) / 2;

2.2.4.查找区间左端点的模板

while (left < right)//这个判断条件一定要注意不要写=
{middle = left + (right - left) / 2;//注意这个if (.....){right = middle;}else{left = middle + 1;}}

查找区间左端点，一定是通过middle来查找到的，而且最终查找到target的时候left一定等于right和middle。说明left所处位置一定是小于target的，所以要不断的去逼近target。所以left一定要加1.
而right是>=target的，有等于target的风险，我们就不能随便乱搞。

另外两个细节，这个其实特别好记忆啊，交给大家一个口诀就是：

移动right或者left的语句出现-号，那就说明上面求middle括号里面就要写+号
移动right或者left的语句出现+号，那就说明上面求middle括号里面就要写-号

不过我不推荐死记硬背，我还是希望大家去好好理解

2.3.二分查找算法（查找区间右端点）

其实和查找区间左端点的差不多，但是我们还是要讲一下里面的细节。

2.3.1.数组划分成两部分

其实和查找区间左端点的差不多，根据右端点把数组分成两部分

左边的这个区间满足<=target，右边的那个区间满足>target，这就具有二分性了。我们就可以使用二分查找算法。

这样子我们就能优化我们的朴素版本的二分查找算法

当nums[middle]<=target的时候，

我们将<和=放到一起来讨论的原因就是当nums[middle]==target的时候，这个位置并不一定是右端点
我们就能发现middle是在左边这个区间的，而我们寻找的右端点就在左边这个区域。
这个时候，我们要怎么移动啊？
我们直接让left更新成middle即可（为啥不更新成middle+1?因为这个是middle可能刚好位于区间右端点，更新成middle+1就可能不符合条件了）

当nums[middle]>target的时候，

我们就能发现middle是在右边这个区间的，而我们寻找的右端点可不是在右边这个区域。所以这个时候把right更新成middle-1即可（因为middle落在的那个点是不符合要求的，要舍去）

接下来就是二分查找最恶心的地方了，就是里面的一些细节

循环条件
求middle的操作

2.3.2.循环条件

什么时候我们执行二分查找操作？

一般就是下面这两种

left<=right的时候
left<right的时候

这个时候我们一定要使用第2种

这个原理和上面查找左端点的一模一样啊！！这里不多赘述。

2.3.3.求middle的操作

我们之前写过两种形式

middle=left+(right-left)/2;
middle=left+(right-left+1)/2;

这两个的区别无非就是数组元素个数是偶数的时候

那么我们这个时候应该使用哪一个呢？

第一种：middle = left + (right - left) / 2;

这是最常用的计算方式。它总是将区间 [left, right] 划分为两个尽可能相等的部分，并向下取整。因此，middle 会偏向左侧。

区间划分：这种方式通常用于查找在[left, right]区间内的元素，并且更新区间时，通常会是[left, middle-1]和[middle+1, right]。
例子：
如果 left = 0，right = 3，那么 middle = 0 + (3 - 0) / 2 = 1。
区间被划分为 [0, 1-1] 和 [1+1, 3]，即 [0, 0] 和 [2, 3]。

第二种：middle = left + (right - left + 1) / 2;

这种方式会将区间 [left, right] 划分为两部分，但 middle 会向上取整。因此，middle 会偏向右侧。

区间划分：这种方式有时用于特定的二分查找变种，比如当需要在某些特定条件下偏向右侧时。更新区间时，可能会是[left, middle-1]和[middle, right]。
例子：
如果 left = 0，right = 3，那么 middle = 0 + (3 - 0 + 1) / 2 = 2。
区间被划分为 [0, 2-1] 和 [2, 3]，即 [0, 1] 和 [2, 3]。

那么我们现在来看看，使用哪一个好呢？

看看middle = left + (right - left) / 2;

假设只有两个不同的元素，如下图

这个时候我们使用middle = left + (right - left ) / 2;求得的middle就位于靠左边那个元素了

这个时候，

假如说nums[middle]>target，按照我们上面的设定，那么right=middle-1，right就会<left，这个时候循环结束，是没有问题的
假如说nums[middle]<=target，按照我们上面的设定，那么left=middle，这个时候无论执行多少次循环，left也是不会动的

所以说，使用middle = left + (right - left ) / 2;是有大问题的

看看middle = left + (right - left + 1) / 2;

假设只有两个不同的元素，如下图

这个时候我们使用middle = left + (right - left + 1) / 2;求得的middle就位于靠右边那个元素了

这个时候，

假如说nums[middle]<=target，按照我们上面的设定，那么left=middle，left就会与right相遇，循环结束，这是没有问题的
假如说nums[middle]>target，按照我们上面的设定，那么right=middle-1，right就会与left相遇，循环结束，这是没有问题的

所以使用middle = left + (right - left + 1) / 2;是没有任何问题的

2.3.4.查找区间右端点的模板

while (left < right)//这个判断条件一定要注意不要写=
{middle = left + (right - left + 1) / 2;//注意这个if (.....){left = middle;}else{right = middle - 1;}}

查找区间右端点，一定是通过middle来查找到的，而且最终查找到target的时候left一定等于right和middle。初始时right所处位置一定是大于target的，所以要不断的去逼近target。所以right一定要减1
而right是<=target的，有等于target的风险，我们就不能随便乱搞。

这个其实特别好记忆啊，交给大家一个口诀就是：

移动right或者left的语句出现-号，那就说明上面求middle括号里面就要写+号
移动right或者left的语句出现+号，那就说明上面求middle括号里面就要写-号

不过我不推荐死记硬背，我还是希望大家去好好理解

2.4.题解

class Solution 
{
public:vector<int> searchRange(vector<int>& nums, int target) {// 处理边界情况：如果数组为空，直接返回{-1, -1}if (nums.size() == 0) {return {-1, -1};}int begin = 0;// 1. 二分查找左端点int left = 0, right = nums.size() - 1;while (left < right){int mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid + 1;}else {right = mid;}}// 判断是否有结果if (nums[left] != target) {return {-1, -1};}else {begin = left; // 标记一下左端点}// 2. 二分查找右端点left = 0, right = nums.size() - 1;while (left < right){int mid = left + (right - left + 1) / 2;if (nums[mid] <= target) {left = mid;}else {right = mid - 1;}}// 返回结果，左端点和右端点return {begin, right};}
};

题目3——69. x 的平方根 - 力扣（LeetCode）

这个题目太简单了，我不想过多讲解

3.1.暴力解法

暴力解法其实非常简单，就依次从0开始往后遍历，每次遍历都计算当前数值的平方是不是和x相同即可

class Solution {
public:int mySqrt(int x) {long long t=0;//使用long long只是为了防止溢出while(t*t<x){t++;}if(t*t==x){return t;}else if(t*t>x) {return t-1;}return -1;//这个只是为了满足编译器需要}
};

3.2.二分查找算法

3.2.1.找数组二段性

在暴力解法里面，我们是不是在遍历一个有序的数组啊？（如下图）我们就找它的二段性

那么我们就可以把这个数组所有元素分成两部分，那怎么分成两半呢？

我们看下面

序列里刚好有t*t==x的

这个时候3*3的平方刚好是等于9的，这个时候无论是使用下面两种分法里面的任何一种都是可以将数组分成两份的，都是符合题目要求的

左边区域是t*t<=x，右边区域是t*t>x（此时结果是左边区域的右端点）
左边区域是t*t<x，右边区域是t*t>=x（此时结果是右边区域左端点）

这样子还不够，我们接着往下看

序列里没有t*t==x的

如果是明确了没有这种t*t==x的，那么我们使用下面这个就能把数组元素分成两半

左边区域是t*t<x，右边区域是t*t>x

但是我们的结果是在哪里呢？

这个时候没有一个数的平方刚好是等于5的，但是我们发现2*2=4<5，3*3=9>5。那么就是要以2或者3为边界来分割数组。这个时候我们仔细看一下题目

这个时候我们发现，它这个最终的结果都是要么直接等于要么就是往左边偏的。

也就是说我们应该返回t*t<x的那个临界点（也就是t*t<x序列的右端点）

那么很显然，t*t<x序列是在数组左边，而在本例中这个2刚好是左边区域的右端点，

综合两种情况来看，两个情况最终的答案都符合t*t<=x的右端点这个位置。

所以我们将使用下面这个方法来将数组所有元素分成两份

左边区域是t*t<=x，右边区域是t*t>x（此时结果就是左边区域的右端点）

3.2.2.left和right的初始位置应该在哪里呢？

我们得知道left必须指向左边区域（t*t<=x），而right必须指向右边区域（t*t>x)

所以left放到0就行（因为0一定是<=x的），right放到x就行（因为x*x一定是>x的）

注意：long long是防溢出的

class Solution {
public:int mySqrt(int x) {long long left=0,right=x;while(left<right){long long middle=left+(right-left+1)/2;if(middle*middle>x){right=middle-1;}else{         left=middle;}}return left;}
};

题目4——35. 搜索插入位置 - 力扣（LeetCode）

这个和第1题有点类似啊

4.1.二分查找

4.1.1.找数组二段性

同样的，我们得把数组分成两块区域？那怎么分呢？

我们往下看

找得到target

这个时候无论是将数组分成下面哪种情况都是能够将数组所有元素分成两半的。

左边区域是nums[i]<=target，右边区域是nums[i]>target（此时结果是左边区域的右端点）
左边区域是nums[i]<target，右边区域是nums[i]>=target（此时结果是右边区域左端点）

这样子看不出来，我们接着往下看

找不到target

找不到target的时候，整个数组所有元素被分成两部分的情况只能是下面这一个

左边区域是t*t<x，右边区域是t*t>x

这个时候我们看看例子

[1,3,4,6,8]，target==5
4<5,而4是左边区域(t*t<x)的右端点
6>5，而6是右边区域(t*t>x)的左端点

大家看一下题目，目标值不在数组里面，就返回它应该被插入的位置，所以它应该被插在6的这个位置，所以返回右边区域(t*t>x)的左端点

综合下来，就只能是

左边区域是nums[i]<target，右边区域是nums[i]>=target（此时结果是右边区域左端点）

有的同学可能直接套公式

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left=0,right=nums.size()-1;while(left<right){long middle=left+(right-left)/2;if(nums[middle]<target){left=middle+1;}else{right=middle;}}return left;}
};

报错了？其实是left和right的问题

4.1.2.left和right的初始位置应该在哪里？

首先我们得知道，我们是按照下面这个进行划分的

左边区域是t<target，右边区域是t>=target

我们得知道left必须位于左边那个区域，right必须位于右边那个区域，只有这样子才能找到我们想要的结果

我们仔细看这种情况

我们发现，这个时候right是一直不动的，而是left是一直middle+1，left是不断逼近right的，直到等于t的。在上面的代码中，我让right=nums.size()-1，即数组最后一个元素。有没有发现这个时候left和right都是位于左边区域（t<target），这个时候你要想找右边区域的左端点，那是不可能的！！

所以我们必须让left指向左边区域，right指向右边区域，如下图

int left=0,right=nums.size();

这样子我们就没有任何问题了

class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left=0,right=nums.size();while(left<right){long middle=left+(right-left)/2;if(nums[middle]<target){left=middle+1;}else{right=middle;}}return left;}
};

题目5——852. 山脉数组的峰顶索引 - 力扣（LeetCode）

这个题目我不详细解释了，因为很简单

5.1.暴力解法

我们应该知道，整个数组的值的大小排列，应该是下面这样子

所以我们只需要从左边开始遍历，直到找到一个数比它后面的数大，那这个数就是峰顶。

class Solution {
public:int peakIndexInMountainArray(vector<int>& arr) {int n=1;while(n<arr.size()&&arr[n-1]<arr[n]){n++;}return n-1;}
};

5.2.二分查找算法

5.2.1.找数组二段性

大家有没有发现，这个数组所有元素被天然的分成了两部分

左边的是情况是，从第2个数开始，当前数都是大于前一个数字的。

也就是说arr[i]>arr[i-1]

右边的情况是，从第1个数开始，当前数都是小于前一个数字的。

也就是说arr[i]<arr[i-1]

所以这个数组尽管是无序的，但是还是可以使用二分查找算法。原因就是它具有二段性

于是，就这样子，我们将数组所有元素分成了两部分

我们要找的就是左边区域的右端点。

mid落在左边区域：arr[mid]>arr[mid-1]，这个时候，我们只需让left=mid即可（因为最终结果在左边区域）
mid落在右边区域：arr[mid]<arr[mid-1]，这个时候我们应该让right=mid-1;

我们发现这个和之前的题目好像一点不同哦！！！这里没有出现等于号！！但是这并不影响数组所有元素都被分成了两部分！！！

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 if(arr[mid]<arr[mid-1]){right=mid-1;}}return left;}
};

当然，由于在这个题目中，是不可能出现arr[mid]==arr[mid-1]的情况的，所以我们还可以像下面这样子写

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 left;}
};

题目6——162. 寻找峰值 - 力扣（LeetCode）

我们只需关注这两个即可

峰值元素是指其值严格大于左右相邻值的元素。
数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
所有有效的i都是nums[i]!=nums[i+1]
nums[-1]=nums[nums.size()]=负无穷

这就意味着，数组里元素的值的走向可能类似下面这两个

上面的只有一个峰值，下面有多个峰值。

6.1.暴力解法

我们完全可以来从第一个元素开始从左往右遍历，只要满足nums[i]<nums[i+1]就i++；如果出现了nums[i]>nums[i+1]，就立即返回i即可

class Solution {
public:int findPeakElement(vector<int>& nums) {int i=-1;for(i=0;i<nums.size()-1;){if(nums[i]<nums[i+1]){i++;}else{break;}}return i;}
};

没有什么难度啊！！！！

6.2.二分查找算法

6.2.1.找数组二段性

我们怎么将数组分成两半呢？

我们可以在数组里面随便找一个位置i，那么我们就可以把情况分成两者

nums[i]>nums[i+1]

这个时候i的左边，也就是[-1,i]，一定有一个峰值（因为nums[-1]=nums[nums.size()]=负无穷），而右边却不一定有峰值，因为有可能从i开始就不断下降。

所以我们得出nums[i]>nums[i+1]的时候，i的左边（包括i）一定存在一个峰值，也就是[-1,i]，右边不一定有。

nums[i]<nums[i+1]

这个时候i的右边，也就是(i,nums.size()-1]，一定有一个峰值（因为nums[-1]=nums[nums.size()]=负无穷），而左边却不一定有峰值，因为有可能从-1开始就不断上升。

所以我们得出nums[i]>nums[i+1]的时候，i的右边（不包括i）一定存在一个峰值，也就是(i,nums.size()-1]，左边不一定有。

nums[mid]>nums[mid+1]的时候

左边一定有峰值，右边不一定有峰值，这个时候我们应该让mid往左边去靠近，那只能移动right，而nums[mid]有可能是i左边（包括i）的峰值，所以我们让right=mid即可。

nums[mid]<nums[mid+1]的时候

左边不一定有峰值，右边一定有峰值，这个时候我们应该让mid往右边去靠近，那只能移动left，这个时候nums[mid]绝对不是是右边的峰值，而nums[mid+1]有可能是右边（不包括i）的峰值，所以我们让left=mid+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]){right=mid;}else{left=mid+1;}}return left;}
};

题目7——153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）

特别关注下面这3个

数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。
nums 中的所有整数 互不相同
nums 原来是一个升序排序的数组，并进行了 1 至 n 次旋转

7.1.暴力解法

题目说要数组的最小值，那我们就直接遍历获取最小值即可

-5000 <= nums[i] <= 5000

class Solution {
public:int findMin(vector<int>& nums) {int res=5001;for(int i=0;i<nums.size();i++){res=min(res,nums[i]);}return res;}
};

7.2.二分查找算法

我们发现，这个是不是能优化呢？我们还没有利用这个数组的特性！！

我们发现旋转后的数组，最大值后面一个都是最小值。如下图

我们发现AB区间里的所有元素都是大于右边元素的！！而且最小值就是CD最左边的元素

我们取数组最后一个元素，也就是CD区间最后一个元素，也就是nums[nums.size()-1]为的值为界限，将数组所有元素分成两部分

AB区间所有元素都满足：nums[i]>nums[nums.size()-1]
CD区间所有元素都满足：nums[i]<=nums[nums.size()-1]

我们要找的就是CD区间的左端点

nums[mid]>nums[nums.size()-1]

中间点落在AB区间，我们要找的不在这里，应该去CD区间找，所以使得left=mid+1;

nums[i]<=nums[nums.size()-1]

中间点落在CD区间，我们要找的就在这个区间的最左边，所以我们让right=mid即可

我们写出代码

class Solution {
public:int findMin(vector<int>& nums) {int left=0,right=nums.size()-1;while(left<right){int mid=left+(right-left)/2;if(nums[mid]>nums[nums.size()-1]){left=mid+1;}else{right=mid;}}return nums[left];}
};

在上面，我使用CD区间最后一个元素的值来当分界点，那我能不能使用AB区间第一个元素的值来当分界点呢？

这个是可以解决的，但是是有一点边界需要处理

特别是下面这种情况

例如，原数组 nums = [0,1,2,4,5,6,7] 在变化后可能得到：

若旋转 7 次，则可以得到 [0,1,2,4,5,6,7]

题目8——LCR 173. 点名 - 力扣（LeetCode）

8.1.暴力解法1——直接遍历

这个直接遍历数组，如果nums[i]！=i，那么我们就返回nums[i]-1;

class Solution {
public:int takeAttendance(vector<int>& records) {int res;for(int i=0;i<records.size();i++){if(i!=records[i]){res=i;break;}}return res;}
};

8.2.二分查找算法

8.2.1.数组的划分

看个例子

我们发现，我们可以将数组分成左右两边区域

左边区域：records[mid]==mid
右边区域：records[mid]>mid

我们要找的就是右边区域的左端点

records[mid]==mid

这个时候，mid位于左边区域，而我们要找的在右边区域的左端点，所以我们让left=mid+1即可

records[mid]>mid

这个时候，mid位于右边区域，而我们要找的在右边区域的左端点，所以我们让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;}
};

这个其实和left和right的指向有问题

8.2.2.left和right的初始位置应该在哪里？

首先我们得知道，我们是按照下面这个进行划分的

左边区域是records[mid]==mid，右边区域是records[mid]>mid

我们得知道left必须位于左边那个区域，right必须位于右边那个区域，只有这样子才能找到我们想要的结果

我们发现边界处理有问题，我们仔细看这个例子，left和right一开始就指向同一个元素，而这个元素是符合左边区域（records[mid]==mid）的要求的。也就是说left和right都指向了左边的这个区域，那mid是不可能找到右边区域的左端点的。所以要修改一下

int left=0,right=records.size();

这样子就不会出现left和right指向同一片区域的情况了

class Solution {
public:int takeAttendance(vector<int>& records) {int left=0,right=records.size();while(left<right){int mid=left+(right-left)/2;if(records[mid]==mid){left=mid+1;}else{right=mid;}}return left;}
};