35.搜索插入位置

解题思路

该题考虑三种情况：

target 在数组中
target 不在数组中，但 target 小于数组最大值
target 不在数组中，且 target 大于数组最大值

对于第一种情况，二分查找的常规操作都能得出正确解。

对于第二种情况，则需要考虑一下插入位置，插入位置应该是第一个大于 target 元素的下标，所以这里要注意 right 不能等于 mid-1，否则就会出现最终返回的下标比正确下标小1的情况。while 循环结束后 left 等于 right，所以返回 left 还是 right 都可以。

对于第三种情况，需要做一下单独的处理， target 的坐标应该插入到数组的最后一位的后面，也就是 nums.length 这个位置。

代码

function searchInsert(nums: number[], target: number): number {
    let len = nums.length;
    let left = 0;
    let right = len - 1;

    // 判断边界情况
    if (nums[len - 1] < target) {
        return len;
    }

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

    return right;
};

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。