leetcode 35. 搜索插入位置

代码：

class Solution {
    public int searchInsert(int[] nums, int target) {
        //去除特殊情况
        if(nums==null||nums.length==0){
            return 0;
        }

        int left=0;
        int right=nums.length-1;

        while (left<right){
            int mid=left+(right-left)/2;

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

        // left 和 right 指针相遇，得到结果
        if(nums[left]<target){
            return left+1;
        }
        return left;
    }
}

题解：

? ? ? ? 本题的意思很清晰，就不分析题意了，我们通过例子来找寻其中的规律

????????输入: nums = [1,3,5,6], target = 5，

????????这种在数组中直接能找到值的就是采用普通的二分法就能找到

????????输入: nums = [1,3,5,6], target = 2

? ? ? ? 当?target 的值在数组中不存在时，我们要将 2 放置到 m 指针指向的位置，我们可以看出，m 指针左边的数据都是小于 target 的数据，m 右边的数据都是 >= target 的数据，所以我们可以将数组划分为两个区域【1】是< target 的区域，【3，5，6】是 >= target 的区域，我们要找到的下标便是 >= target 的区域的左边界

1? ? ? ? 3? ? ? ? 5? ? ? ? 6

? ? ? ? ? m? ? ?

? ? ? ? 以上的分析对于在数组中存在的数据也成立，比如?输入: nums = [1,3,5,6], target = 5，将数组划分为 【1，3】< target 的区间，【5，6】>= target 的区间，此时我们要找的下标也是?>= target 区间的左边界

? ? ? ? 此题采用二分法查找左边界，就能解决

? ? ? ? 对于?输入: nums = [1,3,5,6], target = 2

? ? ? ? 首先，我们计算中点 mid =?left+(right-left)/2 ，mid 指向的值 3 在 >= target 区间 ,不确定 mid 是否已经指向了左边界的位置，所以我们不能跳过 mid ，移动 R 指针 = mid?

1? ? ? ? 3? ? ? ? 5? ? ? ? 6

L? ? ? ?mid? ? ? ? ? ? ? ?R? ?

? ? ? ? 我们再次计算中点 mid = 1在< target 区间，所以 mid 指向的数据肯定不会是左边界，所以直接让 L 指针 = mid+1

1? ? ? ? 3? ? ? ? 5? ? ? ? 6

L? ? ? ? R

mid

? ? ? ? 当 L 和 R 指针指向同一数据时，代表我们成功找到了左边界的值，返回此时的下标即可

1? ? ? ? 3? ? ? ? 5? ? ? ? 6

? ? ? ? ? R

? ? ? ? ? L

? ? ? ? 但存在特殊情况，比如??输入: nums = [1,3,5,6], target = 7，经过查找左边界的流程，最后 L 和 R 指针指向的位置如下，但我们要返回的下标应该是 L+1，所以我们在返回值时要进行判断，当 nums[L] < target 时，返回的下标就应该是 L+1

1? ? ? ? 3? ? ? ? 5? ? ? ? 6

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? L

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? R?