关于二分搜索顺带找到最左匹配点或插入位置的方法及其正确性证明

先上代码：

int searchInsert(vector<int>& nums,int target) 
{
    int n = nums.size();

    int l = 0,r = n;

    while(l < r)
    {
        int mid = (l + r) >> 1;

        if(target <= nums[mid])
        {
            r = mid;
        }
        else
        {
            l = mid + 1;
        }
    }

    return l;
}

首先，我们考虑：

如果对于某个区间[l,r)，令mid = (l + r) / 2，若target = nums[mid]，那么最左位置（也就是target值在单增序列中的第一个出现位置）一定出现在区间[l,mid]中，且有可能出现在区间[l,mid)中。

事实上，若对于一切 x\in [l,mid) ，x都小于nums[mid]，则target = nums[mid] > x，mid就是要找的位置，因此会导致上述区间的上界不变，同时下界会逐渐接近上界（因为上述程序的else分支始终成立）并在下界等于上界时结束，而上界恰好指向了mid，此时l的值就是mid，故算法在这种情况下成立。

然后，我们考虑：

如果对于某个区间[l,r)，若target < nums[mid]，那么有两种情况，若在区间[l,mid)内存在等于某个位置，其值等于target，则正确位置必然在区间[l,mid)内，否则说明序列中不存在值target，由于当索引<mid时，所有的值都不等于target，换句话说就是对于一切 x\in [l,mid) ，x < target，由于target < nums[mid]，则正确的序列插入位置一定是mid，此时会像上一种情况一样，上界被锁定，下界不断接近上界并最终等于上界，此时l = mid，也就是最终答案，故算法在这种情况下成立。

接着，我们考虑：

如果对于某个区间[l,r)，若target > nums[mid]，那么，可以断定，插入位置一定不在mid处，因为，若将nums[mid]推到mid + 1处，将target插入nums[mid]处，此举会造成nums[mid] > nums[mid + 1]，从而违反了序列单增性，同样，匹配位置也不在mid处，因此接下来搜索的区间一定是[mid + 1,r)。

最后，让我们考虑，若序列中存在一个位置，其值等于target，那么二分搜索是否一定能使某次的mid等于该位置？也就是从上述情况2和情况3出发，在“序列中存在一个位置，其值等于target”这一条件下，是否能进入情况1（因为在上述条件下不成立的情况下，其答案的情况已经分析完了，确保了正确性，现在如果能证明在上述条件成立的情况下，会进入情况1，由于情况1的答案已经确定且保证了正确性，因此这将证明整个算法的正确性）。

由上述情况2和情况3的讨论可知，对于当前搜索区间[l,r)，若target < nums[mid]，则必定搜索左区间[l,mid)，若target > nums[mid]，则必定搜索右区间[mid + 1,r)，在不断地缩减区间的过程中，若中间一直没发生target = nums[mid]的情况（若发生，则直接进入情况1，算法就成立了），则一定会导致算法的搜索区间变成[p,p+1)的形式（由于已经证明了若整个序列存在答案的情况下，缩减的序列中一定存在答案，因此该序列中必然存在答案），那么此时，mid = (p + p + 1) / 2 = p（不论p的奇偶性，p + p + 1 = 2p + 1必然为奇数，因此除以2后答案必然为p），那么此时mid = p，此时的p必然是正确位置，从而导致区间缩减到[p,p)的情况下，从而退出循环，此时l = p，算法正确性得证。