关于二分查找的一些细节
最近又重温了一遍二分查找的算法题。发现其中许多细节都是一知半解，看题解时往往会被while循环里到底是用<还是<=,left (right)到底是等于mid还是mid+1(mid-1)等等部分迷惑。这里结合一些资料进行相应的解释。
这里给出了三种模板：
模板一（基本的二分查找）
int left = 0, right = nums.length - 1;
while(left <= right){
int mid = left + (right - left) / 2;
if(nums[mid] == target){ return mid; }
else if(nums[mid] < target) { left = mid + 1; }
else if(nums[mid] > target){ right = mid - 1; }
}
return -1;
}
这是最基础的二分查找，即搜索一个数，如果存在，就返回其索引，否则返回-1。
这里的while循环为什么使用<=而不用<？
因为在初始化right时我们取得是nums.length-1而不是nums.length。我们知道数组的访问末尾是nums.length-1，所以nums.length-1就相当于两端闭区间[left, right]，而nums.length就相当于左闭右开[left,right)（right已经超过数组访问长度)。我们假设target在最后一个下标处，那么一旦我们定义right = nums.length-1，就要保证在最后一个下标处也要进行判断。
找到目标值后就可以停止：if(nums[mid] == target){ return mid; }，那么如果没找到，就需要while循环终止，然后返回-1。while循环在搜索区间为空时终止，意味着区间内没有元素可以找了。
while(left <= right)的终止条件时left = right+1，写成区间形式就是[right+1,right]，即类似于[3,2]这种情况，如果是while(left < right)，那么终止条件为left == right,即[right,right]([2,2])这种情况，那么就会错过2这个数字，这个时候直接返回-1是错误的。
为什么使用left = mid + 1(right = mid - 1)而不是left = mid(right = mid)？
因为当我们发现索引mid不是我们要找到target时，我们需要略过这个数字，即在区间[left,mid-1]或[mid+1,left]内去查询，mid已经搜索过，将其去除。
模板二（寻找左侧边界的二分查找）
int left_bound(int[] nums, int target) {
int left = 0;
int right = nums.length; // 注意
while (left < right) { // 注意
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
right = mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid; // 注意
}
}
return left;
}
这里while循环为什么使用<？
同上面分析的一样，这里right = nums.length，因此每次循环都是在[left,right)区间内进行搜索。其终止条件为left == right，此时搜索区间为空，可以正常终止。
为什么这里要使用right = mid？
因为我们的目的是寻找左侧边界，而搜索区间是[left,right)，也就是说当当前mid的索引被判断之后，我们应该从[left,mid)或[mid+1,right)区间内继续去查找。
如果没有target这个值怎么办？
我们在返回的时候需要可以做一个额外的判断，看nums[left]是否等于target ,如果不等于，就说明target不存在。如果target非常大while一直执行nums[mid] < target，那么left会一直往右移动，直到等于right，退出循环，因此我们还需要判断一下left是否超过了nums.length
while (left < right) {
//...
}
// 此时 target 比所有数都大，返回 -1
if (left == nums.length) return -1;
// 判断一下 nums[left] 是不是 target
return nums[left] == target ? left : -1;
而此模板可以搜索左侧边界的原因就在于当nums[mid] == target时，right=mid，不断的向收缩，达到锁定左侧边界的目的。
模板三（寻找右侧边界的二分查找）
int right_bound(int[] nums, int target) {
int left = 0, right = nums.length;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
left = mid + 1; // 注意
} else if (nums[mid] < target) {
left = mid + 1;
} else if (nums[mid] > target) {
right = mid;
}
}
return left - 1; // 注意
}
能够查找右侧边界的原因就在于当nums[mid] == target时，left = mid+1，即不断的向右侧边界逼近，直到锁定右侧边界。
为什么返回的是left-1而不是left，而且查找的右侧边界，为什么返回的不是right？
因为while循环终止的条件是left == right，所以left和right一样，可以返回right-1，其次，因为当nums[mid] == target时，我们执行的时left = mid+1，因此有可能发生nums[left+1]不等于target
如果不存在target这个值怎么办？
只要在最后判断一下 nums[left-1] 是不是 target 就行了。
类似之前的左侧边界搜索，left 的取值范围是 [0, nums.length]，但由于我们最后返回的是 left - 1，所以 left 取值为 0 的时候会造成索引越界，额外处理一下即可正确地返回 -1。
while (left < right) {
// ...
}
// 判断 target 是否存在于 nums 中
// 此时 left - 1 索引越界
if (left - 1 < 0) return -1;
// 判断一下 nums[left] 是不是 target
return nums[left - 1] == target ? (left - 1) : -1;
这样三种情况就覆盖了大部分二分查找的相关情况。并且在理解了搜索区间的相关概念之后，还可以将三种逻辑进行统一，这里不再进行详细的说明。
例外附上几道比较经典的二分查找算法题，可以试着练练手：
简单：
中等：
这两道题会让我们对二分查找的应用有一个新的认识，建议试试看。
标签：二分,right,target,nums,mid,while,细节,查找,left From： https://www.cnblogs.com/orzzzy/p/16790256.html