为何触发ValueError: -1 not in list错误？有序数组插入位置排查

为什么触发ValueError？ #

你代码里的逻辑是当目标值不在数组中时，取target-1的索引再加1作为插入位置，但**target-1不一定存在于数组中**。比如当输入nums=[1,3,5,6]、target=0时，target-1=-1，而数组里根本没有-1，调用nums.index(x)就会直接抛出-1 is not in list的错误，这就是你看到的报错原因。

代码存在的核心问题 #

• 逻辑假设错误：你默认target-1一定在数组里，但这个假设完全不成立。两种典型场景会触发报错：
  1. 目标值比数组中所有元素都小（比如target=0，数组最小元素是1）
  2. 目标值的前一个数不在数组中（比如nums=[1,4,5]，target=3，target-1=2不在数组里）
• 冗余分支：最后的else分支永远不会执行，因为前面的两个if已经覆盖了target存在或不存在的所有情况，这个分支完全多余。
• 效率低下：用in和index会遍历数组两次，对于有序数组来说，完全可以用二分查找一次遍历搞定，时间复杂度从O(n)降到O(logn)。

修正方案 #

方案1：线性遍历（简单直观） #

遍历数组，找到第一个大于等于目标值的元素索引，就是要返回的位置；如果遍历完所有元素都比目标值小，就返回数组长度。

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        for idx, num in enumerate(nums):
            if num >= target:
                return idx
        return len(nums)

方案2：二分查找（高效最优） #

利用数组有序的特性，用二分查找快速定位目标位置，时间复杂度O(logn)：

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

内容的提问来源于stack exchange，提问作者Giorgi Maisuradze