搜索插入位置

题目

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

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

示例2：

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

解法1：二分法

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;
    }
}

class Solution {
    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;
    }
}