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

约束条件:

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums 包含按升序排列的不重复值
  • -10^4 <= target <= 10^4

解题思路

解题思路

这道题要求在有序数组中查找目标值的位置，如果不存在则返回插入位置，且要求 O(log n) 的时间复杂度，这是典型的二分查找问题。

方法一：标准二分查找 使用经典的二分查找模板。当 nums[mid] < target 时，说明目标值在右半部分，需要向右搜索；当 nums[mid] >= target 时，说明目标值在左半部分或就是当前位置。

方法二：下界查找（推荐） 使用二分查找寻找第一个大于等于 target 的位置。这种写法更加统一，无论目标值是否存在，都能正确返回插入位置。循环结束时，left 指针指向的就是目标值应该插入的位置。

两种方法的核心思想相同，都是通过不断缩小搜索范围来定位目标位置。第二种写法在处理边界情况时更加清晰，是处理此类问题的标准模式。

代码实现

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int left = 0, right = nums.size();
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
};

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)
        
        while left < right:
            mid = (left + right) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid
        
        return left

public class Solution {
    public int SearchInsert(int[] nums, int target) {
        int left = 0, right = nums.Length;
        
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        return left;
    }
}

var searchInsert = function(nums, target) {
    let left = 0, right = nums.length;
    
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(log n)二分查找，每次将搜索范围缩小一半
空间复杂度O(1)只使用了常数个额外变量

相关题目