Search Insert Position — bisect_left in O(log n) [LC 35, Google Microsoft]

Problem Statement#

Given a sorted array of distinct integers nums and a target value, return the index if found; otherwise return the index where it would be inserted to keep the array sorted. Required runtime is O(log n).

Constraints:

• 1 lessequal nums.length lessequal 10^4
• -10^4 lessequal nums[i], target lessequal 10^4
• nums contains distinct values sorted ascending

Input:  nums = [1, 3, 5, 6], target = 5
Output: 2

Input:  nums = [1, 3, 5, 6], target = 7
Output: 4

Why This Problem Matters#

Search Insert Position is often the second binary search problem interviewers assign after LC 704. It looks almost identical but forces you to confront a subtle shift in what you are searching for. In LC 704 you search for an exact match and return -1 when absent. Here there is no "not found" — when the target is absent, you must return the position it would occupy. This changes the template from classic three-way search to left-boundary search, and understanding why is the real lesson.

This problem is also the from-scratch implementation of bisect_left from Python's stdlib and std::lower_bound from C++. Knowing this lets you reach for those functions in contests, but more importantly, being able to implement them from memory in an interview signals genuine algorithmic fluency. Google and Microsoft commonly use LC 35 as the gateway to harder variants: find the first element greater than target, count occurrences in a sorted array, or find the leftmost position satisfying a constraint.

The Core Insight#

The insert position of target is the smallest index i such that nums[i] gte target. If all elements are smaller, the position is len(nums). This is exactly the left boundary: the first index where the condition nums[i] gte target is true.

Set lo = 0, hi = len(nums) — the open right end allows the insert-at-end answer to emerge naturally. If nums[mid] lt target, the position is strictly to the right (lo = mid + 1). Otherwise mid is a valid candidate (hi = mid). When lo == hi, that is the answer.

Visual Dry Run#

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

For target = 7 (insert at end):

Solution (Optimal)#

class Solution:
    def searchInsert(self, nums: list[int], target: int) -> int:
        lo, hi = 0, len(nums)               # open right end for insert-at-end
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if nums[mid] < target:
                lo = mid + 1                # insert position is strictly right
            else:
                hi = mid                    # mid is a candidate
        return lo                            # first index where nums[i] >= target

var searchInsert = function(nums, target) {
    let lo = 0;
    let hi = nums.length;                   // hi can equal length
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        if (nums[mid] < target) {
            lo = mid + 1;                  // need to go right
        } else {
            hi = mid;                      // candidate found
        }
    }
    return lo;                              // insert position
};

Time: O(log n) — single binary search. Space: O(1) — only integer variables.

Common Mistakes#

• Setting hi = len(nums) - 1 prevents lo from reaching len(nums) for end-insertion.
• Using the classic three-way template and returning -1 — this problem requires a position, not an absent flag.
• Returning hi after the loop — works (lo equals hi) but invariant naming should match lo.
• Confusing left-boundary with right-boundary — they answer different questions about duplicates.
• Not testing target-at-start: nums = [5, 7, 9], target = 3 should return 0.

Interview Tips#

• Identify this as bisect_left and mention you are implementing it from scratch.
• Justify hi = len(nums) explicitly — it is the most common bug source.
• Show one in-array and one out-of-range example in your dry run.
• Mention the empty-array edge case: lo = hi = 0, loop skipped, return 0.
• Distinguish from right-boundary by stating whether duplicates affect the answer.

Follow-up Questions#

• How is this related to bisect_left? Exactly equivalent — leftmost position where target could be inserted.
• What if duplicates are present? Returns the first occurrence — bisect_right would return position after them.
• Can you count occurrences of target? right_boundary(target) - left_boundary(target) in O(log n).
• What about an empty array? lo = hi = 0, return 0 — the only valid insert position.
• How does this compare to C++ lower_bound? Identical — both find the first element not less than target.

Key Takeaways#

• Search Insert Position is left-boundary binary search in its purest form.
• The invariant: lo always points to the first index where nums[i] gte target.
• Initialise hi = len(nums) (not len(nums) - 1) to allow insert-at-end.
• The algorithm handles found and not-found uniformly with a single return.
• Identical in semantics to Python's bisect_left and C++ std::lower_bound.
• Counting target occurrences requires both left and right boundaries — see LC 34.
• Time is O(log n) and space is O(1) regardless of where the target lies.