LeetCode/35. 搜索插入位置

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例1 ：

输入: [1,3,5,6], 5
输出: 2

示例2：

输入: [1,3,5,6], 2
输出: 1

示例 3:

输入: [1,3,5,6], 7
输出: 4

示例 4:

输入: [1,3,5,6], 0
输出: 0

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

本题官方提示也说了，就是二分查找，而且就是最最最普通的二分查找，只不过加了一个如果target不存在于nums数组的话要返回插入位置的索引。具体来说，还是二分查找的大框架不变，只需要在最后找不到的时候返回left索引即可，如果非要找出本题的难点，那可能会是left、right值的问题，你到底一开始是选择right = nums.length，还是选择right = nums.length - 1；是选择left = mid，还是left = mid + 1；是right = mid还是right = mid - 1。

具体代码如下：

class Solution {
    public int searchInsert(int[] nums, int target) {
        if (nums.length == 0) return -1;
        int left = 0;
        //这里用right = nums.length，下面的while循环条件就用left < right
        //这里如果是right = nums.length - 1，下面的循环条件就是left <= right
        //这是因为使用right = nums.length循环判等的话会出现越界
        int right = nums.length;

        while (left < right) {
            int mid = left + (right - left) / 2;    //防止left和right太大导致相加除二溢出
            if (nums[mid] == target) {  //如果target就是nums[mid]的值的话就直接返回
                return mid;
            }
            if (target > nums[mid]) {   //如果target比nums[mid]大，我们向右子区间收缩，所以这里需要left = mid + 1
                left = mid + 1;
            }
            if (target < nums[mid]) {
                //因为我们上面的right = nums.length，并且循环条件为left < right
                //所以这里不能使用right = mid - 1，具体的大家可以debug观察结果
                right = mid;
            }
        }
        return left;
    }
}