35. 搜索插入位置 Easy

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

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

示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4

解题思路

输入： 一个递增的有序数组 nums，一个目标值 target

输出： 返回目标值的索引，如果不存在则返回应该放置的索引位置

本题属于基础查找类问题。

我们可以用二分查找的方式快速查找目标值。

每次 nums[mid] > target 时，左指针会移动到 mid + 1，也就是排除掉所有小于 target 的数 每次 nums[mid] < target 时，右指针会移动到 mid - 1，也就是排除掉所有大于 target 的数

当 target 不存在数组中，左指针会停留在所有小于 target 数的右边第一个，也就是 target 应该在的位置

代码实现

python

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        # 初始化左右指针
        l, r = 0, len(nums) - 1

        # 二分查找
        while l <= r:
            mid = (l + r) // 2  # 计算中间位置

            if nums[mid] < target:
                # 目标值在右半部分，移动左指针
                l = mid + 1
            elif nums[mid] > target:
                # 目标值在左半部分，移动右指针
                r = mid - 1
            else:
                # 找到目标值，返回其索引
                return mid

        # 未找到目标值，l 是目标应插入的位置
        return l

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) {
        const mid = Math.floor((left + right) / 2);

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

    return left;
};

复杂度分析

时间复杂度：O(log n)

空间复杂度：O(1)

链接

35 国际版

35 中文版