目录

一、什么是二分查找：

二、算法原理：

1、朴素的二分模板

2、查找左右边界的二分模版：

例题：

模版：

---

一、什么是二分查找：

二分查找又可以称为折半查找，主体思路就是将一组数据找到一个二段性，这样的话就可以经过每次选择就淘汰一部分，不断地缩小一部分，直到最后找到对应的值即可

二分查找并不只是只存在于有序的数组中，而是只要找到一个二段性就能够使用二分查找算法

二、算法原理：

二分查找可以分为3中模版：

1、朴素的二分模板

2、查找左边界的二分模板

3、查找右边界的二分模板

1、朴素的二分模板

比如在数组[1,2,3,4,5,6,7,8,9]中要找到7，那么就有二段性有些数比7小，有些数比7大，那么有了二段性就能够进行二分查找了，

思路：
首先定义left和right定义下标指向数组第一个和最后一个
然后就可以进while循环，结束条件就是left大于right
在循环中就可以找到中间的值，和左边的值，右边的值进行比较
比较逻辑：

如果中间元素等于目标值，则查找成功，返回中间元素

如果中间元素小于目标值，则目标值可能在中间元素的右侧，因此将left更新为mid+1

如果中间元素大于目标值，则目标值可能在中间元素的左侧，因此将right更新为mid-1

如果退出循环了还是没有找到目标值就证明数组中没有目标值，这样返回特定错误值即可

while(left <= right)
{
    int mid = left+(right-left)/2;
    if(...)
        left=mid+1;
    else if(...)
        right = mid-1;
    else 
        return ...;
}

以上就是朴素的二分模版，毕竟比较简单并且局限性很大，就不用例题来讲了

2、查找左右边界的二分模版：

例题：

题目出处：

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/题目说明：

示例说明：

解题思路：

当看到时间复杂度是O(log N)的时候就证明这题如果采用暴力解法是一定会超时的，那么就需要使用二分查找（这也是一个提示）

这题既然是要找一个区间，那么就可以分解为先找到这个区间的左端点，再找到这个区间的右端点，既然用了二分查找，那么就证明需要找到一个二段性，

在本题中，二段性就是   有些元素小于目标元素，有些元素大于等于目标元素，这样可以找到目标元素的左端点；有些元素小于等于目标元素，有些元素大于目标元素，这样可以找到目标元素的右端点，
这也就是所谓查找左右边界的二分模版， 

查找左端点：

如上，当查找左端点的时候，找到的二段性就是小于t和大于等于t，这样
当mid是小于t的时候，就证明此时t的左端点绝对不在mid和mid左边的地方，这个时候就更新left为mid+1
当mid是大于等于t的时候，就证明此时t的左端点绝对在mid和mid左边的地方，这个时候就更新right为mid以查找左端点

循环结束条件：

当left和right相等的时候，此时这个位置就是我所要的结果，退出即可，
所以结束条件是left<right

求中间操作：

这里求中点的操作并不能够是(right+left)/2，因为当left和right都很大的时候数据会溢出，那么求中点公式就是left+(right-left)/2或者是left+(right-left+1)/2

这两个公式的区别是当时偶数情况下的时候，前面的公式就是求的中间偏左一个的，后面的公式就是求中间偏右一个的，那么什么时候用什么呢？这个是根据right的修改就题论题的，当right被更改为mid的时候就不需要+1，当right被更改为mid-1的时候就需要+1

查找右端点：

如上，当查找右端点的时候，找到的二段性就是小于等于t和大于t，这样
当mid是小于等于t的时候，就证明此时t的右端点绝对在mid和mid右边的地方，这个时候就更新left为mid
当mid是大于t的时候，就证明此时t的右端点绝对不在mid和mid左边的地方，这个时候就更新right为mid-1以查找右端点

然后循环结束条件和求中间值和上述查找左端点是几乎一样的

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        //1、找左端点
        int left = 0,right = nums.size()-1;
        if(nums.size() == 0) return {-1,-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 };
        int begin = right;
        //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; 
        }
        if (nums[left] != target) return{ -1,-1 };
        int end = left;
        return {begin,end};
    }
};

题目出处：

852. 山脉数组的峰顶索引 - 力扣（LeetCode）https://leetcode.cn/problems/peak-index-in-a-mountain-array/题目说明：

示例说明：

解题思路：

当会了那两个查找的思路后，其他只要能使用二分查找的题和那些思路差不多，

如在本题中找到一个二段性：当某个元素的值比这个元素的前一个元素的值要大的时候就证明我所要找的峰值肯定不在这个元素的左边（但是可能是这个元素），此时更新left为mid

当某个元素的值比这个元素的前一个元素的值要小的时候就证明我所要找的峰值在这个元素的左边，所以此时更新right = mid-1

只要分析出left怎么变，right怎么变即可直接写代码

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

题目出处：

153. 寻找旋转排序数组中的最小值 - 力扣（LeetCode）https://leetcode.cn/problems/find-minimum-in-rotated-sorted-array/题目说明：

示例说明：

解题思路：

这题看着吓人，但是实际上就是将最后一个元素搞到该数组中的第一个位置，这就是一次旋转

然后就只需要找到二段性和left和right是怎么变的即可

二段性：

首先画出图：

这个时候就可以看到二段性：一部分值比最后一个值要大，另外一部分值比最后一个值要小，那么就可以 以最右边的值作为比较值来二分

left和right的变化：

当mid是大于比较值的话就证明最小值肯定在mid的后面，那么就将left变为mid+1
当mid是小于比较值的话就证明最小值肯定是mid或者在mid的前面，那么就将right变为mid

最后结束循环的时候就是最小值返回即可

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

模版：

找左端点的模版：

while(left < right)
{
    int mid = left+(right-left)/2;
    if(...) left=mid+1;
    else right=mid;
}

找右端点的模版：

while(left < right)
{
    int mid = left+(right-left)/2;
    if(...) left=mid;
    else right=mid-1;
}

在计算mid的时候是否+1取决于right的更新是否-1，如果right更新-1的时候mid计算就需要+1