背景
最近在做力扣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始終滿足nums[right+1] >= target的性質。
不斷更新直至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] >= target。
因此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）。
總結
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;
