算法题/查找类：搜索插入位置

题目

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。（假设数组中午重复元素）
示例1：

输入：[1, 3, 5, 6], 5
输出：2
解释：5存在于数组中，并且所在位置为2

示例2：

输入：[1, 3, 5, 6], 2
输出：1
解释：2不存在于数组中，待插入索引位置为1

解法1：二分法

Java

public class Solution {

    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        // 特殊判断
        if (nums[len - 1] < target) {
            return len;
        }

        // 程序走到这里一定有 target <= nums[len - 1]
        int left = 0;
        int right = len - 1;
        // 在区间 nums[left..right] 里查找第 1 个大于等于 target 的元素的下标
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target){
                // 下一轮搜索的区间是 [mid + 1..right]
                left = mid + 1;
            } else {
                // 下一轮搜索的区间是 [left..mid]
                right = mid;
            }
        }
        // 此时有 left == right，区间缩为一个点，即为答案
        return left;
    }
}

JavaScript

searchInsert(nums, target) {
    let len = nums.length;

    if (nums[len - 1] < target) {
        return len;
    }

    let left = 0;
    let right = len - 1;

    while (left < right) {
        let mid = left + Math.floor((right - left) / 2);
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left;
}