704. 二分查找
模板题
状态：完全掌握三种模板
这题是模板题，用标准思路很快就能写出来，且易于记忆。
我给二分模板定了三要素进行记忆：1.左右初始化；2.while() 条件；3.mid 是否±1。
理解二分的边界是最容易记忆二分的，理解方法是区间不变量原则。为了方便，现在定义的数组都是从小到大顺序排序并且数组从 0 开始。
区间不变量是指将二分的 Left 和 Right 当成区间，同时固定为闭区间还是开区间的不变量。简单来说举个例子：（左闭右开）Left 是闭区间，Right 是开区间，Left 的值是可以取到的，但 Right 的值无法取到。首先看 1.左右初始化：左闭 left 时数组可以取到 left 值，所以 left=0 等于原数组的下标下限，右开 right 取不到，所以 right=nums.size() 比原数组的下标上限多 1 个；2.while() 条件：左闭 left 时数组可以取到 left 值，右开 right 时数组取值不到，right 不能=left 值，所以 while(left<right)；3.mid 是否±1：左闭 left 时数组可以取值，此时 mid=left+right>>1，nums[mid]<target，left 更新，因为 mid 此时的值已经不符合 target 了并且是左闭 left 是可以取到的，所以 left 不取 mid，而是从 mid+1 开始，所以左闭 mid+1。同理，右开 right 时数组取不到 right 的值，nums[mid]>target，right 更新，mid 此时的值不符合 target 并且右开 right 的值是取不到的，所以 right 是可以取到 mid。那左闭右闭则 left=mid+1，right=mid-1；以此类推左开右开 left=mid，right=mid。
我做了个表格以此类推我的理解原则：
| 区间不变量 | 左右初始化 | while() 条件 | mid 是否±1 |
|---|---|---|---|
| 左闭右开 | left=0 | right=nums.size() | left<right | left=mid+1 right=mid |
| 左闭右闭 | left=0 | right=nums.size()-1 | left<=right | left=mid+1 right=mid-1 |
| 左开右开 | left=-1 | right=num.size() | left+1!=right | left=mid right=mid |
最后一行是小金鱼的模板，我记忆为两边都是开的情况，是符合我们的区间不变量原则的，同时没有左开右闭这种情况是因为日常开发中都是用的左闭的多。
下面用左闭右开手撕模板题，模板题是默认了从小到大排列同时没有重复元素的：
class Solution {
public:
int search(vector<int>& nums, int target) {
int left=0,right=nums.size(),middle;
while(left<right) {
middle=left+(right-left)/;
(nums[middle]==target) middle;
(nums[middle]>target)right=middle;
left=middle;
}
;
}
};
