💬 Discord
Sign In
NeetCode #261LC-35EasyBinary SearchNC 250
← Back to All Problems

#261 · #35 · Search Insert Position(搜索插入位置)

📌 Problem Statement & Constraints

Given a sorted array of distinct integers nums and a target, return the index where the target is, or where it should be inserted to keep the array sorted. Constraints: 1 <= nums.length <= 10^4, -10^4 <= nums[i], target <= 10^4.

💡 Core Algorithmic Approaches

  1. This is exactly the lower bound: the first index at which the value is at least the target.
  2. Binary search with lo = mid + 1 when nums[mid] < target, and hi = mid otherwise.
  3. The loop ends at lo == hi, which is the insertion point.
  4. Python's bisect_left implements precisely this, so the built-in is a legitimate answer.

💻 Benchmark Python3 Implementation

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        lo, hi = 0, len(nums)      # note: hi is exclusive here
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] < target:
                lo = mid + 1       # target must be to the right
            else:
                hi = mid           # mid is a candidate answer
        return lo


# Built-in equivalent
class Solution2:
    def searchInsert(self, nums: List[int], target: int) -> int:
        from bisect import bisect_left
        return bisect_left(nums, target)

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(log n): the search space halves each iteration.
💾 Space Complexity
O(1): two indices.

⚠️ Interview Pitfalls & Follow-ups

  • Using hi = len(nums) - 1: the insertion point can be len(nums) (when the target is larger than every element), so the exclusive bound hi = len(nums) is needed.
  • Using hi = mid - 1: that would skip the candidate at mid; the correct form is hi = mid.
  • Returning mid: the loop ends at lo == hi, which is the answer.
  • Handling the empty array: lo = hi = 0 immediately returns 0, which is correct and needs no special case.