搜索插入位置

🟢 Easy · 🏷️ 数组、二分查找 · LeetCode#35

📖 题目

在升序数组 nums 里找 target 的下标；找不到就返回它应该被插入的位置。

输入	输出	说明
nums=[1,3,5,6], target=5	2	找到了
nums=[1,3,5,6], target=2	1	插入位置
nums=[1,3,5,6], target=7	4	插入末尾

💡 思路

这题是二分查找的变形：代码几乎一样，唯一区别是找不到时返回什么。

左闭右闭的二分查找，循环结束时一定是 i > j，而且此时 i 正好指向第一个大于 target 的位置——也就是 target 该插入的地方。这是左闭右闭写法的一个自然结果，不用额外处理。

💻 代码

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        i, j = 0, len(nums) - 1
        while i <= j:
            m = (i + j) // 2
            if nums[m] == target:
                return m
            if nums[m] > target:
                j = m - 1
            else:
                i = m + 1
        return i   # 找不到时，i 就是插入位置

时间复杂度 O(log n)，空间复杂度 O(1)。跟二分查找相比，只有最后一行 return -1 换成了 return i。