二分查找上下界问题的思考
背景
最近在做力扣hot100中的二分查找题目时，发现很多题目都用到了二分查找的变种问题，即二分查找上下界问题，例如以下题目：
35. 搜索插入位置
74. 搜索二维矩阵
34. 在排序数组中查找元素的第一个和最后一个位置
它们不同于查找等于target的位置，而是查找大于等于或者小于等于的位置，经过思考后总结出以下的思路，以35题“搜索插入位置”为例，这一题的插入位置即为第一个大于等于target的位置，以下是我的最终代码：
class Solution {
public:int searchInsert(vector<int>& nums, int target) {int left = 0, right = nums.size() - 1, mid;while(left <= right){mid = (left + right) / 2;if(nums[mid] < target)left = mid + 1;elseright = mid - 1;}return left;}
};
推导
最初我看了他人的代码之后感觉非常懵逼，为什么返回的是left呢？left为什么是第一个大于等于target的索引呢？思考了好一阵才想明白，我们来分析这里left和right的含义，重点在于它们的初始化和更新条件。
首先left初始化为0，0左侧没有任何元素，left左侧的值小于等于target的性质成立。
之后left的每次更新，通过将left = mid + 1带入到条件nums[mid] < target之中，我们可以得到left始终满足nums[left-1] < target。
与之类似的，right始终满足target <= nums[right+1]的性质。综合这两个性质为nums[left-1] < target <= nums[right+1]。
不断更新直至left > right，更准确的说循环结束时left = right+1，考虑最后一次循环：
- 如果 left == right：
- 如果 nums[mid] < target，那么 left = mid + 1 = right + 1，循环结束
- 如果 nums[mid] >= target，那么 right = mid - 1 = left - 1，循环结束
- 如果 left + 1 == right，此时 mid = left：
- 如果 nums[mid] < target，那么 left = mid + 1 = left + 1 = right，下一次循环会进入情况1
- 如果 nums[mid] >= target，那么 right = mid - 1 = left - 1，此时 right < left，循环结束
因此，无论哪种情况，当循环结束时，都会有 left = right + 1。
在left和right都在数组索引[0, nums.size()-1]的范围内的情况下，将left = right+1带入left和right的性质得到nums[right] < target <= nums[left]。
因此nums[left-1] < target <= nums[left]且nums[right] < target <= nums[right+1]，理解为left是第一个大于等于target的索引位置， right是第一个小于target的索引位置。
示例
以下图为例：
输入: nums = [1,3,5,6], target = 5
首先初始化left和right分别为0和3，然后计算得到mid等于1，由于索引1的值（3）小于target（5）。
因此left移动到mid+1（也就是2）的位置，说明在**2左侧（红色范围，不包括2）**的所有值都小于target的值（5）。接下来计算得到mid等于2，由于索引2的值（5）大于等于target（5）。
因此right移动到mid-1（也就是1）的位置，说明**1右侧（黄色范围，不包括1）**的所有值都大于等于target的值（5）。
注意到结束时left和right的位置印证了上面的证明，即left=right+1，left指向right右侧第一个位置，left及右侧的所有值都大于等于target。right指向left左侧第一个位置，right及左侧所有值都小于target。
总结
if(nums[mid] < target)left = mid + 1;
elseright = mid - 1;
因此当我们设置以上的条件时，最终left和right都在数组范围内的情况下，left一定是第一个大于等于target的索引位置（因为nums[left-1] < target <= nums[left]），right一定是第一个小于target的索引位置（因为nums[right] < target <= nums[right+1]）。
反之，如果我们设置以下的条件，最终left一定是第一个大于target的索引位置，right一定是第一个小于等于target的索引位置。
if(nums[mid] <= target)left = mid + 1;
elseright = mid - 1;