Search Insert Position

Problem

Given a sorted array of distinct integers nums and a target value target, return the index of target if it is present. If it is not present, return the index where it would be inserted to keep the array sorted.

Your algorithm must run in O(log n) time.

Examples

• Input: nums = [1, 3, 5, 6], target = 5 → Output: 2 (5 is present at index 2.)
• Input: nums = [1, 3, 5, 6], target = 2 → Output: 1 (2 belongs between 1 and 3, at index 1.)
• Input: nums = [1, 3, 5, 6], target = 7 → Output: 4 (7 is larger than every element, so it goes at the end.)

Constraints

• 1 <= nums.length <= 10^4
• -10^4 <= nums[i], target <= 10^4
• nums contains distinct values sorted in ascending order.
• Required time complexity: O(log n).

Think about it first

TL;DR

Lower-bound binary search (first index with nums[i] >= target) — O(log n) time, O(1) space.

Approach 1 — Brute force (linear scan)

Walk the array left to right and stop at the first element that is >= target; that index is the answer whether the target is present (equal) or absent (greater). If you never stop, the target belongs at the end.

def searchInsert(nums: list[int], target: int) -> int:
    for i, x in enumerate(nums):
        if x >= target:
            return i
    return len(nums)

Time O(n), space O(1). Passes at n <= 10^4, but the problem mandates O(log n) and the scan ignores the sortedness entirely.

Approach 2 — Lower-bound binary search

Both cases reduce to one question: find the first index whose element is >= target (the array length if none is). The predicate nums[i] >= target is False for a prefix and True for the rest, so the boundary between them is monotone and binary search can find the first True. This is the classic lower bound: the leftmost position where the value can be inserted while keeping the array sorted.

def searchInsert(nums: list[int], target: int) -> int:
    lo, hi = 0, len(nums)          # hi is exclusive; answer may be len(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1           # boundary is strictly right of mid
        else:
            hi = mid               # mid could be the boundary
    return lo

Walkthrough on nums = [1, 3, 5, 6], target = 2:

1. lo=0, hi=4 → mid=2, nums[2]=5 >= 2 → hi=2.
2. lo=0, hi=2 → mid=1, nums[1]=3 >= 2 → hi=1.
3. lo=0, hi=1 → mid=0, nums[0]=1 < 2 → lo=1.
4. lo == hi == 1 → return 1.

There is no separate “found” check: a present target and an absent one run through the same code. Time O(log n), space O(1).

Approach 3 — The standard library (bisect_left)

Python provides this lower bound directly. bisect.bisect_left(nums, target) returns the leftmost insertion point that keeps nums sorted, the same value Approach 2 computes.

import bisect


def searchInsert(nums: list[int], target: int) -> int:
    return bisect.bisect_left(nums, target)

Walkthrough on nums = [1, 3, 5, 6], target = 7: every element is < 7, so the leftmost valid insertion point is 4, the array length.

Time O(log n), space O(1). In an interview, write Approach 2 to demonstrate the mechanics, then mention this one to show you know the standard library.

Common pitfalls

• Initializing hi = len(nums) - 1 with the lo < hi convention — the “insert at the very end” answer (len(nums)) becomes unreachable, failing targets larger than every element.
• Handling “found” and “not found” as separate code paths. The lower-bound formulation makes them the same; special-casing invites off-by-ones.
• Using the bisect_right boundary (first index with nums[i] > target) — with distinct values it differs from bisect_left exactly when the target is present, returning one past the match instead of the match.
• Mixing conventions: hi = mid belongs with exclusive hi and while lo < hi; hi = mid - 1 belongs with inclusive hi and while lo <= hi. Blending them loops or skips.

Pattern takeaway

When a binary-search problem asks for a position rather than a match, reframe it as boundary-finding: define a monotone predicate (here nums[i] >= target), then find the first index where it turns True. The half-open [lo, hi) lower-bound template handles the found, not-found, and end-of-array cases with no special-casing, which makes it one of the most reusable binary-search variants.