【C++算法】二分查找 -＞ 入门
二分，我********
二分查找的介绍
二分查找的特点
在二分查找中，它是最恶心，细节最多，最容易写出死循环的算法，但是只要我们把它弄清楚，去理解，最恶心就会变得最简单了
学习中的侧重点
1、算法原理
使用二分查找，不止可以在数组有序得情况去使用，在我们理解的深刻，那么我们也可以发现一些规律，即使在数组无序中，我们也可以去使用二分优化
2、模板
我们学习二分，一定要去理解模板，不要去死记硬背，理解之后再去记忆，才能发挥最大的功能！
二分查找模板一共有3个：
朴素的二分模板虽然比较简单，但是它有一定的局限性，左边界和右边界其实也算我们的万能模板
开始学习！
一、二、三，上链接！
704. 二分查找 - 力扣（LeetCode）
（一）朴素的二分模板
二分查找算法原理：
1.二分查找算法的本质是利用数组的有序性和二段性进行高效搜索。
2.二段性：通过比较中间元素，将数组分成两个子数组，根据比较结果舍去一部分，继续在另一部分搜索。
3.适用范围：不仅限于有序数组，只要满足二段性即可。
二段性，就是分半，mid = left + (right - left)/2;
例如：在一堆数组，我们要找target
1、如果这个数组，比5小的，也就是1~4，不是我们的目标值，我们是不是可以舍去？答案是的
目标值在5~7的区间里
2、继续搜，是不是如果比5大的，我们也不要呢？答案是的
3、在搜索，如果mid == target，此时这个就是我们的答案，可以直接返回了
最后，为什么可以不要这些值？因为他不是我们需要的值呀，人家要找5，你搜6和7的区间有个屁用？
二分查找算法细节问题：
1.定义left和right指针，初始化搜索区间。
2.循环条件：left <= right。
3.在循环中，计算中间元素的索引mid，并与目标值进行比较。
4.根据比较结果更新left或right指针，缩小搜索区间。
5.如果找到目标元素，返回其索引；如果未找到，返回-1。
class Solution { public: int search(vector<int>& nums, int target) { int left = 0, right = nums.size() - 1; while(left <= right) { int mid = left + (right - left) / 2;//防止溢出 if(nums[mid] < target) left = mid + 1; else if(nums[mid] > target) right = mid - 1; else return mid; } return -1; } };mid，为什么这样子写？
int left = 2,000,000,000; // 20亿 int right = 2,000,000,000; // 20亿 int mid = (left + right) / 2; // left + right = 40亿 ❌ 超过 int 最大值 21.47亿！left = 1,500,000,000 right = 2,000,000,000 right - left = 500,000,000 // ✅ 差值很小，不会溢出 mid = 1,500,000,000 + 250,000,000 = 1,750,000,000 // ✅ 正确34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
（二）查找左边界的二分模板
我们找7，第一个出现的7
为什么r要等于mid？
这仅适用于
arr[mid] > target的情况（mid 值已大于 target，mid 及其右边都不可能等于 target）。但如果arr[mid] == target，mid 可能是答案，不能r=mid-1，而应r=mid保留 mid。
为什么l要等于mid+1？
如果
arr[mid] < target，整个[l, mid]区间都小于 target，不可能有答案，所以应l = mid+1（排除）。如果arr[mid] >= target，答案可能在[l, mid]，此时不是l=mid，而是r=mid（向左收缩）。
（三）查找右边界的二分模板
同理：
l=mid
arr[mid] <= target：mid 及其左边都可能 ≤ target，但我们想要最右边的，所以答案可能在[mid, r]区间（因为 mid 可能就是答案，也可能右边还有）。此时应保留 mid，收缩左边界：l = mid。
r=mid
arr[mid] > target：mid 的值已经大于 target，那么 mid 及其右边都肯定不是答案，直接排除：r = mid - 1
细节讨论：
循环条件：
left < right √
- 当left == right的时候，就是最终结果
- 如果判断容易造成死循环
中点位置：
①left + (right - left) / 2→左中位数（偏左）
②left + (right - left + 1) / 2→右中位数（偏右）
看一个极端例子：
left=0, right=1。
如果找最后一个，逻辑是
if (arr[mid] <= target) l = mid;
用公式①（偏左，mid=0）→
l = 0，区间[0,1]没变，死循环。用公式②（偏右，mid=1）→
l = 1，区间变为[1,1]，正常退出。如果找第一个，逻辑是
if (arr[mid] >= target) r = mid;
用公式②（偏右，mid=1）→
r = 1，区间[0,1]没变，死循环。用公式①（偏左，mid=0）→
r = 0，区间变为[0,0]，正常退出。
题目ac代码：
class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { if(nums.size()==0)return {-1,-1}; int begin=0; // 1、找左端点 int l=0,r=nums.size()-1; while(l<r) { int mid=l+(r-l)/2; if(nums[mid]<target) { l=mid+1; }else { r=mid; } } if(nums[l] != target) return {-1,-1}; else begin=l; // 2、找右端点 l=0,r=nums.size()-1; while(l<r) { int mid=l+(r-l+1)/2; if(nums[mid]<=target) { l=mid; }else{ r=mid-1; } } return {begin,r}; } };总结模板：