目录
二分查找
【左闭右闭】/【相错终止】
【循环不变量】
【四要素】
二分查找的任意模板
【一般】情形
【左闭右闭】总结
mid的防溢出写法
【左闭右开】/【相等终止】
【一般】情形
再谈初始值
【左闭右开】总结
二分查找本质
【左开右闭】/【相等终止】
【一般】情形
【左闭右开】总结
【左开右开】/【相邻终止】
二分查找总结
二分查找
核心思想：通过不断将搜索区间分成两半，排除不可能存在目标值的部分，从而缩小搜索范围，直到找到目标或确定目标不存在
我们后续会在【左闭右闭】总结时，讲解二分查找的本质
虽然二分查找的基本思想比较简单，但其中的细节却极易容易出错。
本文会讲解二分查找的三种常见实现模板(额外讲解一个【左开右闭】)以及其中细节
例如：
1.左右边界的初始值的几种组合(left=0,right=nums.length-1/left=0,right=nums.length/.....)
2.【左闭右闭】、【左闭右开】、【左开右开】在代码中如何实现的?
3.在while循环中，何时使用 <，何时使用<= ?
4.关于中间值下标的写法由来(mid=(left+right)/2、mid=left+(right-left)/2)
5.左右边界更新语句到底怎么写(left=mid+1,right=mid-1/left=mid+1,right=mid/......)
6.关于返回值，到底是left还是right，right-1，left+1...
本文希望大家在看完二分查找本质后，能够清楚上述细节的解答，以及能够自己写出【左开右闭】以及【左开右开】的代码。
【左闭右闭】/【相错终止】
相等返回：有相等元素时返回等于下标，否则返回-1
首先我们先通过一个简单题目来学习关于【左闭右闭】在代码中的实现
题目链接：704. 二分查找 - 力扣（LeetCode）
题目描述：
给定一个
n个元素有序的（升序）整型数组nums和一个目标值target，写一个函数搜索nums中的target，如果目标值存在返回下标，否则返回-1。
示例 1:输入:nums = [-1,0,3,5,9,12], target= 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4示例 2:
输入:nums = [-1,0,3,5,9,12], target = 2 输出: -1 解释: 2 不存在 nums中因此返回 -1提示：
- 你可以假设
nums中的所有元素是不重复的。n将在[1, 10000]之间。nums的每个元素都将在[-9999, 9999]之间。
解题代码：
class Solution {
public static int search(int[] nums, int target) {
int n=nums.length;
int left=0;
int right=n-1;
while(left<=right){//循环条件
int mid=(left+right)/2;//中间值坐标
if(nums[mid]==target)return mid;//相等时，返回下标
else if(nums[mid]>target)right=mid-1;//#1更新后right右侧元素都大于target
else left=mid+1;//#2更新后left左侧元素都小于target
}
return -1;
}
}【循环不变量】
循环不变量的核心思想是：
·在每次循环迭代开始时，确保left和right所定义的区间是有效的，即目标元素要么位于该区间内，要么已被排除
·在每次循坏迭代结束时，更新left和right的值，以缩小查找范围，同时保持新的查找范围仍然有效
为了实现上述思想，我们需要找到一些在整个循环过程中都不会发生变化的【量】或【关系】，以便得到循环结束后某些确定的结论。在这个实现中，上述代码中#1和#2两行保证了如下【关系】是【循环不变】的：
1.对于#1行，若进入该分支，则right下标更新后，其右侧元素都大于target
2.对于#2行，若进入该分支，则left下标更新后，其左侧元素都小于target(如下图)
在程序运行过程中，当中间值(nums[mid])等于target时，直接返回结果。否则，继续执行#1或#2，基于上述两个【循环不变】的关系，若执行#1，则更新后，right右侧元素都将大于target；若执行#2，则更新后，left左侧元素都将小于target。这样每次循环都可以排除一半的元素。注意，这两个循环不变的关系，在更新后会一直存在。切记，一定是更新后。因为如果target比nums中所有元素都大，那么right将不会被更新；如果target比nums中所有元素都小，那么left也不会被更新。不经历更新，就不具有上述两条【循环不变】的关系。例如，target大于nums中所有元素时，right将不会被更新，最终right=nums.length-1,left=nums.length，这里只有left经历了更新，说明此时left左侧的元素都小于target是正确的，但是right右侧元素都大于target是不成立的(right右侧没有元素)。
当循环因不满足循环条件(left<=right)而终止时，我们观察一下left和right的关系。
如上图所示，left和right刚好错开时，循环终止。此时，left左侧的元素都小于target，right右侧的元素都大于target。这两者覆盖了整个数组nums，表示在该数组中找不到target。
【四要素】
从上述代码和分析中，我们可以总结出二分查找中的四要素为：初始值、循环条件、mid的计算方式、左右边界更新语句。
二分查找的任意模板
·while中的等号和left，right的更新语句决定了二分查找循环终止时left和right的位置关系(相错/相等/相邻)
·left，right的初始值和mid的计算方式要使得中间下标mid覆盖且仅覆盖【搜索空间】中所有可能的下标
我们上述讲解了 相等返回(要求返回等于target的数字下标)，接下来我们讲解四种【一般】情形，所谓【一般】是指要求返回大于等于/大于/小于等于/小于target的数字下标。我们这里将与target相等的元素的下标称作【等于下标】，大于target的元素中最小的那个下标称作【刚好大于下标】，同理有【刚好小于下标】，在找不到要求元素时，我们返回-1.
【一般】情形
情形1--大于等于
大于等于：有相等元素时返回等于下标，否则返回刚好大于下标；否则返回-1
代码如下：
public static int search(int[] nums,int target){
int left=0;
int right=nums.length-1;
while(left<=right){
int mid=(left+right)/2;
if(nums[mid]<target)left=mid+1;//#1更新后，left左侧元素都小于target
else right=mid-1;//#2更新后，right右侧元素都大于等于target
}
return left==nums.length?-1:left;//处理：相等/刚好大于/不存在
}【循环不变】的【关系】：
对于#1行，若进入该分支，则left下标更新后，其左侧元素都小于target
对于#2行，若进入该分支，则right下标更新后，其右侧元素都大于等于target
所以target一定不会在left左侧，而right的右侧必定大于等于target，又因为nums是有序的，因此可以得出，left要么是等于下标，要么刚好是大于下标。需要注意的是，这里循环不变的关系只保证了在循环期间，左右侧元素与target的关系，并不能保证left或right最终一定在nums的下标范围内。实际上则有可能超出一位，即当nums中的所以元素都大于等于target(right=-1)或都小于target(left=nums.length)时。
关于返回语句( left==nums.length?-1:left)的解释：
考虑nums中元素的三种情况：
1.nums中所有元素都小于target时，right不更新，最终left=nums.length，因此当这个关系成立时，返回-1
2.nums中存在元素大于等于target时，由【循环不变】的关系可知，最终应该返回left
3.nums中所有元素都大于等于target时，left不更新，left=0，最终right=-1，此时应当返回下标0，因此返回left
情形2--大于
大于：不考虑相等，返回刚好大于下标；否则返回-1
考虑nums中元素的三种情况：
1.nuns中所有元素都小于等于target时，right不更新，最终left=nums.length，因此当这个关系成立时，应当返回-1
2.nums中存在元素大于target时，由【循环不变】的关系可知，最终应该返回left
3.nums中所有元素都大于target时，left不更新，left=0，最终right=-1，此时应当返回下标0，因此返回left
代码：
public static int search(int[] nums,int target){
int left=0;
int right=nums.length-1;
while(left<=right){
int mid=(left+right)/2;
if(nums[mid]<=target)left=mid+1;//更新后，left左侧元素都小于等于target
else right=mid-1;//更新后，right右侧元素都大于target
}
return left==nums.length?-1:left;//处理：刚好大于/不存在
}情形3--小于等于
小于等于：有相等元素时返回等于下标，否则返回刚好小于下标；否则返回-1
考虑nums中元素的三种情况：
1.nums中所有元素都小于等于target时，right不更新，right=nums.length-1，最终left=nums.length，此时应该返回right
2.nums中存在元素小于等于target时，由【循环不变】的关系可知，最终应该返回right
3.nums中所有元素都大于target时，left不更新，left=0，最终right=-1，此时应当返回-1，因此返回right
代码：
public static int search(int[] nums,int target){
int left=0;
int right=nums.length-1;
while(left<=right){
int mid=(left+right)/2;
if(nums[mid]<=target)left=mid+1;//更新后，left左侧元素都小于等于target
else right=mid-1;//更新后，right右侧元素都大于target
}
return right;//处理：相等/刚好小于/不存在
}情形4--小于
小于：不考虑相等，返回刚好小于下标；否则返回-1
考虑nums中元素的三种情况：
1.nums中所有元素都小于target时，right不更新，right=nums.length-1,最终left=nums.length，因此应该返回right
2.nums中存在元素小于target时，由【循环不变】的关系可知，最终应该返回right
3.nums中所有元素都大于等于target时，left不更新，left=0，最终right=-1，此时应该返回-1，因此返回right
public static int search(int[] nums,int target){
int left=0;
int right=nums.length-1;
while(left<=right){
int mid=(left+right)/2;
if(nums[mid]<target)left=mid+1;//更新后，left左侧元素都小于target
else right=mid-1;//更新后，right右侧元素都大于等于target
}
return right;
}【左闭右闭】总结
核心在于【相错终止】，即循环终止时，right=left-1。【左闭右闭】的标志是while中的循环条件left<=right以及left和right更新时的left=mid+1，right=mid-1(更新语句)，两者相辅相成，共同作用实现了【相错终止】。另外left和right的初始值的【左闭右闭】也是一大特点
简单来说，循环条件+更新语句+(初始值)--->【相错终止】
通过left左侧和right右侧的【循环不变】关系，确定while终止后的目标下标。在【一般】情形中，要考虑不更新导致的越界及其对应的返回前判断
mid的防溢出写法
我们在上述代码中都是使用int mid=(left+right)/2的形式来计算数组中间下标。
注意：这里的mid是向下取整的，假设(left+right)2=5.5，由于mid是int类型，最终存储在mid的值其实是5。(向下取整)
当right的值接近int类型的值，并且left很接近right时，(left+right)可能会超过int类型的最大值，导致溢出，最终得到的结果会不正确。所以我们采用 mid=left+(right-left)/2 (向下取整)来计算数组中间下标。
在后面的学习中，可能还会用到向上取整，即 mid=(left+right+1)/2 。为了防止提前溢出，也可以采用 mid=left+(right-left+1)/2 。
【左闭右开】/【相等终止】
【左闭右开】的特点就在于【相等终止】，即当while终止时，left=right(所以循环条件设置为left<right)。由【左闭右闭】可知，left与right在while循环终止时的关系由循环条件和它们的更新语句(和初始值)所决定。
我们先研究【初始值】，如果left和right的初始值设置为与【左闭右闭】相等，即left=0，right=nums.length-1，那么由于while的循环条件是left<right，当nums只有一个元素时，将无法进入while循环，因此为了能够至少进入一次while循环，我们【左闭右开】中right的初始值应该设置为right=nums.length。还有，当nums中所有元素都小于target时，right=nums.length是这一情况的一个标志；如果right=nums.length-1，只看right的最终取值是无法判断为nums中所有元素都小于target的，仍需要比较一次target与nums中的最后一个元素。
我们之前已经说过，【左右边界初始值】的设置需和中间下标mid配合，使得mid的取值能够覆盖且仅覆盖【搜索空间】中所有可能的下标。要满足这个要求，也必须取left=0，right=nums.length。这就是所谓的【左闭右开】，右开--表示该值无法取到，和数学中所学一致
代码如下：
public static int search(int[] nums,int target){
int left=0;
int right=nums.length;//注意right初始值的设置
while(left<right){
int mid=(left+right)/2;
if(nums[mid]==target)return mid;
else if(nums[mid]<target)left=mid+1;//#1更新后，left左侧元素都小于target
else right=mid;//#2更新后，right及其右侧元素都大于target
//虽然right没有跳过mid处的元素，但更新后的right已不在搜索区间内了
}
return -1;
}这里【循环不变】的关系为：
1.对于#1行，若进入该分支，则left下标更新后，其左侧元素都小于target
2.对于#2行，若进入该分支，则right下标更新后，right处及其右侧元素都大于target
在程序运行过程中，当中间值等于target时，直接返回结果。否则，继续执行#1或#2，基于上述两个【循环不变】的关系。若执行#1，则更新后，left左侧元素都将小于target；若执行#2，则更新后，right及其右侧元素都大于target。
而当left=right时，此时循环终止。如下图所示：
当while终止时，right及其右侧和left左侧正好覆盖了nums的所有元素。此时可以得知：target不存在于nums中。若target大于nums中的所有元素，虽然right不更新，但最终left的左侧将覆盖所有元素(left=right=nums.length)。同样地，当target小于nums中的所有元素时，虽然left不更新，但最终right及其右侧覆盖了所有元素。
【一般】情形
情形1--大于等于
大于等于：有相等元素时返回等于下标，否则返回刚好大于下标；否则返回-1
考虑nums中元素的三种情况：
1.nums中所有元素都小于target时，right不更新，最终left=right=nums.length，因此当这个关系成立时，返回-1
2.nums中存在元素大于等于target时，由【循环不变】的关系可知，最终可以返回left/right(相遇)
3.nums中所有元素都大于等于target时，left不更新，left=0，最终right=left=0，此时应当返回下标0，因此返回right/left
代码如下：
public static int search(int[] nums,int target){
int left=0;
int right=nums.length;//注意right初始值的设置
while(left<right){
int mid=(left+right)/2;
if(nums[mid]<target)left=mid+1;//更新后，left左侧元素都小于target
else right=mid;//更新后，right右侧元素都大于等于target
}
return right!=nums.length?right:-1;//根据nums中元素的三种情况对应的返回前判断得出
}注意：关于我们最后返回的代码，只是因为我们是在【有相等元素时返回等于下标，否则返回刚好大于下标；否则返回-1】的前提下，而得来的
接下来，我们通过下面的题目来看看与上述讲解有何不同
题目链接：35. 搜索插入位置 - 力扣（LeetCode）
题目描述：
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为
O(log n)的算法。示例 1:
输入: nums = [1,3,5,6], target = 5 输出: 2示例 2:
输入: nums = [1,3,5,6], target = 2 输出: 1示例 3:
输入: nums = [1,3,5,6], target = 7 输出: 4提示:
1 <= nums.length <= 10^4-10^4 <= nums[i] <= 10^4nums为 无重复元素 的 升序 排列数组-10^4 <= target <= 10^4
题目分析：根据题目定义以及示例，我们可以知道本题就是寻找第一个大于等于target的数字下标，但与我们之前所讲【不同】的是：如果target不存在时，返回它将会被按顺序插入的位置。
所以，我们只需要调整返回语句即可
解题代码：
class Solution {
public int searchInsert(int[] nums, int target) {
int left=0;
int right=nums.length;//注意right初始值的设置
//找到第一个大于等于target的数字下标
while(left<right){
int mid=(left+right)/2;
if(nums[mid]<target)left=mid+1;//更新后，left左侧元素都小于target
else right=mid;//更新后，right右侧元素都大于等于target
}
return left==nums.length?nums.length:left;
}
}情形2--大于
考虑nums中元素的三种情况：
1.nums中所有元素都小于等于target时，right不更新，最终left=right=nums.length，因此当这个关系成立时，应当返回-1
2.nums中存在元素大于target时，由【循环不变】的关系可知，最终应该返回right/left
3.nums中所有元素都大于target时，left不更新，left=0，最终right=left=0，此时应当返回下标0，因此返回right/left
解题代码：
public static int search(int[] nums,int target){
int left=0;
int right=nums.length;
while(left<right){
int mid=(left+right)/2;
if(nums[mid]<=target)left=mid+1;//更新后，left左侧元素都小于等于target
else right=mid;//更新后，right右侧元素都大于target
}
return right!=nums.length?right:-1;
}情形3--小于等于
考虑nums中元素的三种情况：
1.nums中所有元素都小于等于target时，right不更新，最终left=right=nums.length，因此当这个关系成立时，应当返回right-1/left-1(即nums.length-1)
2.nums中存在元素小于等于target时，由【循环不变】的关系可知，最终应该返回right-1/left-1
3.nums中所有元素都大于target时，left不更新，left=0，最终right=left=0，此时应当返回-1，因此返回right-1/left-1
解题代码：
public static int search(int[] nums,int target){
int left=0;
int right=nums.length;
while(left<right){
int mid=(left+right)/2;
if(nums[mid]<=target)left=mid+1;//更新后，left左侧元素都小于等于target
else right=mid;//更新后，right右侧元素都大于target
}
return right-1;
}情形4--小于
考虑nums中元素的三种情况：
1.nums中所有元素都小于target时，right不更新，最终left=right=nums.length，因此当这个关系成立时，应当返回right-1/left-1(即nums.length-1)
2.nums中存在元素大于target时，由【循环不变】的关系可知，最终应该返回right-1/left-1
3.nums中所有元素都大于等于target时，left不更新，left=0，最终right=left=0，此时应当返回下标-1，因此返回right-1/left-1
解题代码：
public static int search(int[] nums,int target){
int left=0;
int right=nums.length;
while(left<right){
int mid=(left+right)/2;
if(nums[mid]<target)left=mid+1;//更新后，left左侧元素都小于target
else right=mid;//更新后，right右侧元素都大于等于target
}
return right-1;
}再谈初始值
我们这里令n=nums.length-1
初始值：在【左闭右闭】中，right=n，而在【左闭右开】中，right=n+1。
【左闭右开】：该取值的主要原因是当target大于nums中所有元素时，right不更新，那么right=n+1将是判断这一情况的标志。如果right的初始值为n，由于右开的原因，会导致最后一个元素不在搜索区间内。即：循环终止后right不变，则无法知道究竟是target大于nums中的所有元素，还是target为最后一个元素。
由于很多题目的答案保证了在搜索区间内必有解(即在[0,n]区间内能找到符合要求的下标)，此时right的初始值就不需要设置为n+1。虽然这会导致无法考察到n处的元素，但并不会影响返回值的正确性，接下来我们简单分析一下
·【相等返回】情形：返回的是mid。若答案为最后一个元素，left=right=n时循环结束。由于【相等返回】是在循环中返回mid下标的，而我们循环结束时，无法进入循环，从而无法更新mid下标，最终导致无法处理target是最后一个元素的情况
·【大于等于】&【大于】情形：返回的是right。若答案为最后一个元素(所以right不进行更新)，left=right=n时循环结束。在循环结束前，left和right相邻，由于nums[mid]<target/nums[mid]<=target来更新left=mid+1，然后left和right相遇于最后一个元素，此时刚好返回right
·【小于等于】&【小于】情形：返回的是right-1。若答案为最后一个元素，而返回的right-1=n-1，无法返回n。但可以通过判断nums[right-1]是否满足需求，不满足时表示答案为最后一个元素。返回语句此时大致可以这么写：return nums[right - 1] <= target ? right - 1 : right;
那在我们处理【大于等于】&【大于】/【小于等于】&【小于】情形时，初始值到底选择n还是n+1呢？
通常我们只需要按照right=n+1来写即可，但需要注意，当有些题目已保证在搜索空间中必有解的情况下，我们需要判断n+1在本题中会不会导致越界问题。如果不会导致越界，两者皆可用；否则，我们需要使用right=n。当然，在满足right=n不影响返回值的正确性时，也可以初始化right=n来省去对越界情况的分析。
【左闭右开】总结
·核心在于【相等终止】，即循环终止时，left=right。【左闭右开】的标志是while中的循环条件left<right以及left和right更新时的left=mid+1,right=mid(左右边界更新语句)，两者相辅相成，共同作用实现了【相等终止】。另外left和right的初始值的【左闭右开】也是一大特点
简单来说，循环条件+更新语句+(初始值)--->【相等终止】
通过left左侧和right右侧的【循环不变】关系，确定while终止后的目标下标。在【一般情形】中，要考虑边界不更新导致的越界问题及其对应的返回前判断
二分查找本质
通过有序性/二段性对搜索空间进行快速排除，将时间复杂度从线性O(n)优化到对数级O(log n)。其核心在于以下三点：
一、有序性/二段性：二分查找的根基
前提条件：数组必须有序(升序或降序)
为什么重要？
有序性/二段性使得我们通过单次比较，直接排除一半无效数据。
例如：针对【左闭右闭】情形
·若nums[mid]<target，则左半区间[left,mid]的所有值都小于目标，可直接排除，无需逐个检查
·若nums[mid]>target，则右半区间[mid,right]的所有值都大于目标，同样直接排除
这里的二段性并不等于有序性。那什么是二段性呢？
二段性是指可以将数组分为两个部分，每个部分内部有某种特定的性质。比如前半部分满足某个条件，后半部分不满足，或者相反。
例如，在旋转排序数组中，数组被旋转后，可能会被分成两个递增的部分，比如[4,5,6,7,0,1,2]。这时候数组的前半部分都比后半部分大，或者类似的情况。在这种情况下，虽然整个数组不是完全有序的，但可能依然可以使用二分查找来找到特定的元素，或者找到旋转点。
二分查找的关键就在于每次能够根据中间元素的情况，确定接下来应该搜索左半部分还是右半部分。二段性中这个条件的存在使得即使数组不是全局有序的，仍然可以利用二分法逐步缩小范围
总结一下，当数组具有二段性时，存在一个分界点，使得分界点前后元素的性质不同。二分查找正是利用这个分界点的存在，通过不断调整搜索区间来定位这个分界点或者目标元素的位置。每次比较中间元素后，可以确定分界点在左半部分还是右半部分，从而将问题规模减半。
注意：如果数组的二段性无法通过中间元素直接判断属于哪一段，或者分界点的位置无法通过简单的比较来确定，这时候可能需要更复杂的处理，或者无法应用二分查找
二、分治策略：快速缩小问题规模
核心操作：每次将搜索区间一分为二，仅保留可能包含目标值的区间，舍弃另一半
数学原理：每次操作后，问题规模减半(n-->n/2-->n/4-->...-->1)，最终只需log2 N次操作即可完成搜索
实现关键：通过循环不变量严格维护搜索区间的有效性。例如：
·左闭右开区间[left，right)：始终保证目标值(若存在)在[left，right)内，直到区间为空
·调整边界的精确性：通过mid的计算和边界移动(left=mid+1,right=mid)，确保每一步都严格缩小搜索范围
三、循环不变量：保证正确性的核心
1.定义：在循环的每一步，目标值(若存在)必须位于当前区间内。例如：
·初始时：区间为[0，nums.length-1]，覆盖整个数组
·迭代中：根据nums[mid]与target的比较，调整left或right，确保目标值始终在新区间内
2.实现要点
·中点的计算形式(向上/向下取整)：
取决于区间定义(左闭右开或左开右闭)，需确保区间缩小后不陷入死循环。例如：
·左闭右开[left，right)--->中点向下取整(mid=(left+right)/2 )-->确保mid能够让left移动：由于向下取整，mid较小，使得nums[mid]的值较小，更可能使left右移，以缩小区间
·左开右闭(left，right]--->中点向上取整(mid=(left+right+1)/2 )-->确保mid能够让right移动
·边界调整的对称性：必须与区间定义和中点计算形式严格匹配，否则会导致区间遗漏或死循环
【左开右闭】/【相等终止】
【左开右闭】的特点也是【相等终止】，即当while终止时，left=right(所以循环条件也为left<right)。
我们这里依旧先研究【初始值】，如果left和right的初始值设置为与【左闭右闭】相等，即left=0,right=nums.length-1，那么由于while的循环条件是left<right，当nums只有一个元素时，将无法进入while循环。因此为了能够至少进入一次while循环，我们【左开右闭】中left的初始值应该设置为left=-1。还有，当nums中所有元素都小于target时，left=-1是这一情况的一个标志；如果left=0，只看left的最终取值是无法判断为nums中的所有元素都小于target的，仍需要比较一次target与nums中的第一个元素。
代码如下(当target大于等于最后一个元素时会死循环)：
public static int search(int[] nums,int target){
int left=-1;
int right=nums.length-1;
while(left<right){
int mid=(left+right)/2;
if(nums[mid]==target)return mid;
else if(nums[mid]<target)left=mid;//更新后，left左侧元素都小于target
else right=mid-1;//更新后，right右侧元素都大于等于target
}
return -1;
}
public static void main(String[] args) {
int[] nums={3,4,5,6,7};
int target=2;//当target为7 8 9，会死循环
int temp=search(nums,target);
System.out.println(temp);
}注意：
上述死循环的原因是：当left指针走到下标为3的位置处，right指针处于下标为4的位置处时，mid的取值一直为3，导致left指针一直在下标为3的位置处，无法终止循环。
所以，总结这里死循环的原因，由于left=mid，并且从某一时刻开始，mid的取值不变时(left指针不移动)，会导致死循环。
为了解决死循环，我们采取向上取整的mid形式(即mid=(left+right+1)/2 防提前溢出形式：mid=left+(right-left+1)/2 )，因为mid向上取整，它会比较大(让元素大一些)，能够保证让right指针移动，从而使得每次循环都能缩小区间，避免死循环
正确代码：
public static int search(int[] nums,int target){
int left=-1;
int right=nums.length-1;
while(left<right){
int mid=left+(right-left+1)/2;
if(nums[mid]==target)return mid;
else if(nums[mid]<target)left=mid;//更新后，left左侧元素都小于target
else right=mid-1;//更新后，right右侧元素都大于target
}
return -1;
}【一般】情形
情形1--大于等于
考虑nums中元素的三种情况：
1.nums中所有元素都小于target时，right不更新，right=nums.length-1,最终left=right=nums.length-1，因此应该返回-1
2.nums中存在元素大于等于target时，由【循环不变】的关系可知，最终应该返回right+1/left+1
3.nums中所有元素都大于等于target时，left不更新，left=-1，最终right=-1，此时应该返回0，因此返回left+1/right+1
代码：
public static int search(int[] nums,int target){
int left=-1;
int right=nums.length-1;
while(left<right){
int mid=left+(right-left+1)/2;
if(nums[mid]<target)left=mid;//更新后，left左侧元素都小于target
else right=mid-1;//更新后，right右侧元素都大于等于target
}
return left==nums.length-1?-1:left+1;
}为什么这里的left和right相遇，我画在了左边一侧呢？
其实是因为在【左开右闭】，由于向上取整的mid形式，确保了在左右指针相邻时，mid的向上大致其变大，使得right指针移动(左移)。所以会导致在左侧相遇
情形2--大于
考虑nums中元素的三种情况：
1.nuns中所有元素都小于等于target时，right不更新，最终left=right=nums.length-1，因此当这个关系成立时，应当返回-1
2.nums中存在元素大于target时，由【循环不变】的关系可知，最终应该返回left+1/right+1
3.nums中所有元素都大于target时，left不更新，left=-1，最终right=-1，此时应当返回下标0，因此返回left+1/right+1
代码：
public static int search(int[] nums,int target){
int left=-1;
int right=nums.length-1;
while(left<right){
int mid=left+(right-left+1)/2;
if(nums[mid]<=target)left=mid;//更新后，left左侧元素都小于target
else right=mid-1;//更新后，right右侧元素都大于等于target
}
return left==nums.length-1?-1:left+1;
}情形3--小于等于
考虑nums中元素的三种情况：
1.nums中所有元素都小于等于target时，right不更新，最终left=right=nums.length-1，因此当这个关系成立时，应当返回nums.length-1(即left/right)
2.nums中存在元素小于等于target时，由【循环不变】的关系可知，最终应该返回right/left
3.nums中所有元素都大于target时，left不更新，left=-1，最终right=-1，此时应当返回-1，因此返回right/left
代码：
public static int search(int[] nums,int target){
int left=-1;
int right=nums.length-1;
while(left<right){
int mid=left+(right-left+1)/2;
if(nums[mid]<=target)left=mid;//更新后，left左侧元素都小于等于target
else right=mid-1;//更新后，right右侧元素都大于target
}
return right;
}情形4--小于
考虑nums中元素的三种情况：
1.nums中所有元素都小于target时，right不更新，最终left=right=nums.length-1，因此当这个关系成立时，应当返回nums.length-1(即left/right)
2.nums中存在元素小于target时，由【循环不变】的关系可知，最终应该返回right/left
3.nums中所有元素都大于等于target时，left不更新，left=-1，最终right=left=-1，此时应该返回-1，因此返回right/left
代码：
public static int search(int[] nums, int target) {
int left = -1;
int right = nums.length - 1;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (nums[mid] < target) left = mid;//更新后，left左侧元素都小于target
else right = mid - 1;//更新后，right右侧元素都大于等于target
}
return right;
}【左闭右开】总结
核心在于【相等终止】，即循环终止时有left=right。【左闭右开】的标志是while中的循环条件left<right以及left和right更新时的left=mid+1，right=mid(更新语句)，两者相辅相成，共同作用实现了【相等终止】。另外left和right的起始值的【左闭右开】也是一大特点
简单来说，循环条件+更新语句+(初始值)--->【相等终止】
通过left左侧和right右侧的【循环不变】关系，确定while终止后的目标下标。在【一般】情形中，要考虑左右边界不更新时导致的越界及其对应的返回前判断
【左开右开】/【相邻终止】
【左开右开】的特点在于【相邻终止】，即当while终止时，left+1=right(所以循环条件设置为left+1<right)。由【左闭右闭】可知，left与right在while循环终止时的关系由循环条件和它们的更新语句(和初始值)所决定
通过【左闭右开】以及【左开右闭】，我们这里猜测【左开右开】的初始值应该设置为：
left=-1，right=nums.length。这样就保证了搜索区间[0，nums.length-1]处于(-1，nums.length)内。
【相等返回】情形
代码：
public static int search(int[] nums,int target){
int left=-1;
int right=nums.length;
while(left+1<right){
int mid=(left+right)/2;
if(nums[mid]==target)return mid;
if(nums[mid]<target)left=mid;//#1更新后，left左侧元素都小于target
else right=mid;//#2更新后，right右侧元素都大于target
}
return -1;
}这里【循环不变】的关系为：
1.对于#1行，若进入该分支，则left下标更新后，left及其左侧元素都小于target
2.对于#2行，若进入该分支，则right下标更新后，right及其右侧元素都大于target
在程序运行过程中，当中间值(nums[mid])等于target时，直接返回结果。否则，继续执行#1或#2。
基于上述两个【循环不变】的关系，若执行#1，则更新后，left及其左侧元素都小于target；若执行#2，则更新后，right及其右侧元素都小于target。这样每次循环都可以排除一半的元素。注意，这两个【循环不变】的关系，在更新后会一直存在。切记，一定是更新后。
当循环因不满足循环条件而终止时，我们观察一下left和right的关系
如上图所示，left和right刚好相邻时，循环终止。此时，left及其左侧元素都小于target，right及其右侧元素都大于target。这两者覆盖了整个数组nums，表示在该数组中找不到target
这里，我们就不再一一写出【左开右开】的【一般】情形了。无非是在判断语句加不加等于号，或者返回语句该如何写的问题。
二分查找总结
要想写好二分查找，牢记下面4个步骤：
1.确定区间形式(【左闭右闭】、【左闭右开】、【左开右开】.....)
2.维护区间形式(搜索空间)：为了维护区间形式，要设计初始值、循环条件、左右边界。
例如：
当区间形式为【左闭右闭】/【相错终止】时：
初始值：令left=0,right=nums.length-1。这样便保证了整个数组都在搜索范围[left,right]内。
循环条件：当两者相错时，才终止循环。所以循环条件设计为：left<=right。
左右边界：在每次搜索完后，需要排除已经搜索过的区间。由于我们这里区间为【左闭右闭】，所以[left，mid](或者[mid，right])区间内的元素都被搜索过，那么更新边界后，新的搜索区间就需要去除mid处的元素。所以需要设置：left=mid+1/right=mid-1（去除掉上一次搜索过的元素）
当区间形式为【左闭右开】/【相等终止】时：
初始值：因为右侧是不包含的，而我们需要让整个数组都在搜索范围内，所以需要设置right=nums.length，即搜索范围为：[0，right)--->覆盖了整个数组
循环条件：当两者相遇时，才终止循环。所以循环条件设计为：left<right
左右边界：因为区间为【左闭右开】，由于左侧是【闭】，右侧为【开】；所以左侧不变，我们这里只看右侧边界。虽然[left，mid]区间内的元素都被搜索过，但是由于我们新的搜索区间右侧是不包括的，所以设置为right=mid(去除mid下标处的元素)。如果right=mid-1，这样会导致搜索区间遗漏mid-1下标处的元素
3.区间调整：通常都是采取向下调整。但是有时候需要向上调整。如后续讲的【左开右闭】。判断当左右指针相邻时，是否会发生死循环。如果发生死循环，则需要向上调整的mid形式，使得mid处的元素能够帮助循环缩小区间(让right指针左移)，避免无限循环。
简单来说，我们需要让 mid的形式(向上调整/向下调整)帮助循环缩小区间。
向上调整(如：【左开右闭】)--让右侧指针左移(mid处的元素较大) 来缩小区间(通常右侧为闭区间)
向下调整(如：【左闭右开】)--让左侧指针右移(mid处的元素较小) 来缩小区间(通常左侧为闭区间)
因为在【左开右闭】/【左闭右开】中，一侧指针移动到mid处后，可能会导致死循环。所以采取特定的中点计算形式，让另一侧指针多移动，以避免死循环。
注意：如果区间形式是【左闭右闭】/【左开右开】区间，我们都采取向下调整
4.结果验证：通过分析nums中元素的三种情况以及其对应的返回值判断(可以像上述一样画图来增加理解)，得出返回结果
