35.搜索插入位置

难度：简单

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

请必须使用时间复杂度为 O(log n) 的算法。

示例 1:

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

示例 2:

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

示例 3:

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

提示:

• 1 <= nums.length <= 104
• -104 <= nums[i] <= 104
• nums 为 无重复元素 的 升序 排列数组
• -104 <= target <= 104

解题思路

和 704 题很像，但是这次是如果没有找到指定的数字，需要返回这个数字应该插入的位置。

要求算法复杂度为 O(log n)，同时已给数组是 有序且无重复 的，可以考虑使用二分查找。

难点在于没有找到指定数字时，如何确定这个数字应该插入的位置，我的思路是：

1. 在找不到指定数字的最后一次循环开始前，此时 left = right = middle 成立
2. 如果 nums[middle] < target，那么应该插入的位置是 middle 的后一位
3. 如果 nums[middle] > target，那么应该插入的位置是 middle 本身的位置，也就是取代 middle 的位置

想清楚第 2 步和第 3 步的区别，这道题也就简单了

我的代码

public int searchInsert(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    return binarySearch(nums, left, right, target);
}

public int binarySearch(int[] nums, int left, int right, int target) {
    int result = -1;
    while (left <= right) {
        int middle = left + (right - left) / 2;
        if (nums[middle] == target) {
            result = middle;
            break;
        } else if (nums[middle] < target) {
            result = middle + 1;
            left = middle + 1;
        } else if (nums[middle] > target) {
            result = middle;
            right = middle - 1;
        }
    }
    return result;
}

时间复杂度：O(log n)

空间复杂度：O(1)

另一种思路

1. 在找不到指定数字的最后一次循环开始前，此时 left= right = middle 成立
2. 如果 nums[middle] < target，那么会执行 left = middle + 1= right + 1，此时应该插入的位置是 middle 的后一位，也就是 更新后的 left，同时也是 right + 1
3. 如果 nums[middle] > target，那么会执行 right = middle - 1= left - 1，此时应该插入的位置是 middle 本身的位置，也就是取代 middle 的位置，也就是 left，同时也是 更新后的 right + 1
4. 那么当循环结束的时候，返回 left 或者 right + 1都可以

public int searchInsert(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    return binarySearch(nums, left, right, target);
}

public int binarySearch(int[] nums, int left, int right, int target) {
    while (left <= right) {
        int middle = left + (right - left) / 2;
        if (nums[middle] == target) {
            return middle;
        } else if (nums[middle] < target) {
            left = middle + 1;
        } else if (nums[middle] > target) {
            right = middle - 1;
        }
    }
    //return left;
    return right + 1;
}

时间复杂度：O(log n)

空间复杂度：O(1)

上述思路和我的思路的区别在于：

• 我用 result 暂存了返回值，因为我不能确定 result 最后一次赋值是在什么时候，所以我需要频繁给他赋值，只需要保证最后一次得到的是目标值就可以了，而上述思路中不用 result，减少了赋值的开销
• 上诉思路是在执行对 left 和 right 的变动之后，才对目标值的位置进行寻找，找到了目标值位置出现的共性，完成了对以下三种情况的统一处理：
• 目标值在数组所有元素之前
• 目标值插入数组中的位置
• 目标值在数组所有元素之后

总结

只要看到面试题里给出的数组是有序数组，都可以想一想是否可以使用二分法。

同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的。