{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Search Insert Position – Solution & Complexity

Interview solutions
/
Search Insert Position

Solution Walkthrough

  1. Step 1: Understand the Return Value

    • If target exists in the sorted array, return its index.
    • If it does not exist, return the position where it could be inserted while keeping the array sorted.
    • That insertion position is the first index whose value is greater than or equal to target.

  2. Step 2: Linear Scan Idea

    • A simple solution checks values from left to right.
    • Return the first index where nums[i] >= target.
    • This is easy but O(n), while the problem asks for O(log n).
    def search_insert(nums, target):
    for i, num in enumerate(nums):
        if num >= target:
            return i
    return len(nums)

  3. Step 3: Use Binary Search

    • Because nums is sorted, binary search can discard half of the remaining positions each step.
    • Keep a search window [left, right) where right is exclusive.
    • The answer will be the smallest index where the value is at least target.

  4. Step 4: Move the Bounds

    • If nums[mid] < target, the insertion point must be to the right of mid.
    • Otherwise, mid might be the answer, so keep it by moving right to mid.
    • When the window is empty, left is the insertion index.
    def search_insert(nums, target):
    left, right = 0, len(nums)
    while left < right:
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

  5. Step 5: Final Complete Solution

    • The same binary search handles found and not-found cases.
    • Time complexity is O(log n) because the window halves each iteration.
    • Space complexity is O(1).
    def search_insert(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
Learn the Binary Search pattern: recognition cues, invariant, and ordered practice →

FAQ

See also

Practice Search Insert Position online (run code in the browser)Binary Search solution (easy)Find Minimum in Rotated Sorted Array solution (medium)Koko Eating Bananas solution (medium)Longest Increasing Subsequence solution (hard)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?