[LeetCode] 35. Search Insert Position

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

Example 1:
Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:
Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:
Input: nums = [1,3,5,6], target = 7
Output: 4

Constraints:
1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums contains distinct values sorted in ascending order.
-104 <= target <= 104

搜索插入位置。

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/search-insert-position
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

二分法基础题。给一个数字和一个有序数组，如果这个数字在数组中存在，返回其坐标；否则返回它应该被插入的位置。

二分法不难想到，但是面试的重点是你如何能把二分法写对。我个人比较喜欢第一种实现方法。注意 while 循环的条件，比如我下面的代码，left <= right，你可以这样想，最后 while 跳出循环的时候，一定是 left > right（与 while 里的条件相反），在 while 循环的最后一步的时候，left == right，再走一步就跳出了 while 循环的条件了。同时，当我们找到任何一个 mid 但是 mid 上的元素不满足条件的时候，为什么 right = mid - 1（left = mid + 1）？那是因为 mid 位置上的元素一定不满足条件了，所以在确定新的边界的时候可以将 mid 去掉。

复杂度

时间O(logn)
空间O(1)

代码

Java实现一

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    while (left <= right) {
        let mid = Math.floor(left + (right - left) / 2);
        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
};

Java实现二

因为右边界 right = nums.length 在定义的时候就事实上已经越界了，下标最多是到 nums.length - 1 的。所以当 mid > target 的时候，right = mid，是为了确保 mid 也在被扫描的范围内。

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

JavaScript实现

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function(nums, target) {
    let left = 0;
    let right = nums.length - 1;
    while (left <= right) {
        let mid = Math.floor(left + (right - left) / 2);
        if (nums[mid] === target) {
            return mid;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return left;
};

相关题目

35. Search Insert Position
704. Binary Search