Search Insert Position (LeetCode 35)

The problem

You get a sorted array nums of distinct integers and a target. If target is in the array, return its index. If not, return the index where it would be inserted to keep the array sorted. It must run in O(log n).

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

2 is not present. It belongs between 1 and 3, which is index 1.

How to think about it

Start with brute force. Scan from the left and return the first index whose value is >= target. If none, return len(nums). That is correct but O(n).

Both cases ask the same question. If the target is present, its index is the first position with a value >= target. If it is absent, the insertion point is also the first position with a value >= target. So the problem is really: find the first index i where nums[i] >= target. This is called the lower bound.

The key insight: “is nums[i] >= target?” is a sorted yes/no question. Along a sorted array the answers look like no, no, no, yes, yes. You want the first yes, the boundary. Binary search finds a boundary in O(log n): if nums[mid] >= target, the boundary is at mid or to the left (hi = mid); otherwise it is strictly to the right (lo = mid + 1). Start with hi = len(nums) so “insert at the end” is a possible answer.

Which pattern is this? Binary search for a boundary. The tell is “first position where something becomes true” on sorted data. Python ships this as bisect.bisect_left, and saying so in an interview shows fluency, as long as you can also write the loop by hand.

Approach

1. The answer is the lower bound of target: the smallest i with nums[i] >= target, or len(nums) if there is none.
2. bisect.bisect_left(nums, target) returns exactly that.
3. By hand: lo, hi = 0, len(nums); while lo < hi, take mid; if nums[mid] < target set lo = mid + 1, else hi = mid. Return lo.

Solution

import bisect

def search_insert(nums, target):
    return bisect.bisect_left(nums, target)   # first index with nums[i] >= target
# search_insert([1,3,5,6], 5) -> 2
# search_insert([1,3,5,6], 2) -> 1

Dry run

bisect_left runs the half-open loop from step 3 of the approach. On nums = [1, 3, 5, 6], target = 2:

Now lo == hi == 1, so the answer is 1. For target = 7 the search walks right (lo goes 3, then 4) and returns 4, the end of the array.

Complexity

• Time: O(log n). The range [lo, hi) halves on every step.
• Space: O(1).

Edge cases and pitfalls

• Target larger than everything returns len(nums), which is why hi starts at len(nums), not len(nums) - 1.
• Target smaller than everything returns 0.
• Empty array returns 0.
• Mixing templates: with hi = mid you must loop on lo < hi, not lo <= hi, or you can loop forever.
• With duplicates, bisect_left gives the first copy and bisect_right gives the position after the last. Choose deliberately.

Related problems

• Binary Search (LeetCode 704): the exact-match template this boundary search grows out of.
• Find First and Last Position of Element in Sorted Array (LeetCode 34): lower bound plus upper bound.
• First Bad Version (LeetCode 278): the same “first yes” boundary, with an API call as the test.