力扣之二分法

        今天，学习了二分法，详细内容见代码随想录 (programmercarl.com)，讲得十分好。

        力扣之35. 搜索插入位置 - 力扣（LeetCode）。

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while(left <= right){
            int mid = left + (right - left)/2;
            if(nums[mid] < target){
                left = left + 1;
            }
            else if(nums[mid] > target){
                right = mid -1;
            }
            else
            return mid;
        }
        return left;
    }
};

        这里与直接二分法稍微不同，存在数组中并没有target,还要找到target插入的位置，这里用了一句return left就解决了。

        这里其实可以自己动手画画，如果找不到target,最后的right是小于left的，而且left = right + 1，left的位置就是第一个大于target的数字的位置，就是target要插入的位置。

        二分法的场景有很多，比如已经知道数组中是有target，这个比较简单，还有一种就是target是不在数组中的，但最后跳出循环的时候，【right，left】区间就是包含target所在的范围。还有一种是数组中有许多target，要确定上下限，这得分别用二分法确定上下限。

        二分法的关键词：已排序，查找对应数据。

附录：

代码随想录 (programmercarl.com)