35. Search Insert Position

Leetcode link

题目简介

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */

题目给我们一个升序数字数组 nums 以及一个数字 target

要求我们返回 target 在数组中的下标；如果不存在，则返回 target 插入数组的时候应该在的下标

要求 logn 的时间复杂度

解题思路

要求 logn 的复杂度的已排序数组搜索，我们优先使用二分搜索来做

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 = (left + right) >> 1

        if (nums[mid] === target) {
            return mid
        } else if (nums[mid] > target) {
            right = mid - 1
        } else {
            left = mid + 1
        }
    }

    return left
};