二分搜索模板

给一个有序数组和目标值，找第一次/最后一次/任何一次出现的索引，如果没有出现返回-1

模板四点要素

1、初始化：start=0、end=len-1
2、循环退出条件：start + 1 < end
3、比较中点和目标值：A[mid] ==、 <、> target
4、判断最后两个元素是否符合：A[start]、A[end] ? target

注意：为了防止overflow，超过int范围，左中位数（a+b)=a+(b-a)/2,右中位数（a+b)=a+(b-a+1)/2如果有mid*mid,mid用int注意溢出

时间复杂度 O(logn)，使用场景一般是有序数组的查找

典型示例

704. 二分查找

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int start,mid,end;
        start=0;
        end=nums.size()-1;
        
        while(start<=end)
        {
            mid=start+(end-start)/2;//防止两数之和超过int范围
            if(nums[mid]==target)
                return mid;
            if(nums[mid]>target)
            {
                end=mid-1;
            }
            else{
                start=mid+1;
            }
            
        
        }
        return -1;

    }
};

大部分二分查找类的题目都可以用这个模板，然后做一点特殊逻辑即可

另外二分查找还有一些其他模板如下文，大部分场景模板#3 都能解决问题，而且还能找第一次/最后一次出现的位置，应用更加广泛

所以用模板#3 就对了

模板 #1 (left <= right)

二分查找的最基础和最基本的形式。
查找条件可以在不与元素的两侧进行比较的情况下确定（或使用它周围的特定元素）。
不需要后处理，因为每一步中，你都在检查是否找到了元素。如果到达末尾，则知道未找到该元素。

模板 #2 (left < right)

一种实现二分查找的高级方法。
查找条件需要访问元素的直接右邻居。
使用元素的右邻居来确定是否满足条件，并决定是向左还是向右。
保证查找空间在每一步中至少有 2 个元素。
需要进行后处理。当你剩下 1 个元素时，循环 / 递归结束。需要评估剩余元素是否符合条件。

模板 #3 (left + 1 < right)

实现二分查找的另一种方法。
搜索条件需要访问元素的直接左右邻居。
使用元素的邻居来确定它是向右还是向左。
保证查找空间在每个步骤中至少有 3 个元素。
需要进行后处理。当剩下 2 个元素时，循环 / 递归结束。需要评估其余元素是否符合条件。

如果是最简单的二分搜索，不需要找第一个、最后一个位置、或者是没有重复元素，可以使用模板#1，代码更简洁

总结

二分搜索核心四点要素（必背&理解）

1、初始化：start=0、end=len-1
2、循环退出条件：start + 1 < end
3、比较中点和目标值：A[mid] ==、 <、> target
4、判断最后两个元素是否符合：A[start]、A[end] ? target