{ }DevToolsDaily
ToolsInterview
Problems
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Search Insert Position – Solution & Complexity

Interview solutions
/
Search Insert Position

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. 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. 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. 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. 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

FAQ

See also:

Practice Search Insert Position online (run code in the browser)Binary Search solution (easy)Longest Increasing Subsequence solution (hard)Median of Two Sorted Arrays solution (hard)Best Time to Buy and Sell Stock solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?