Search Insert Position

Given a sorted array and a target, return the index if the target is found. Otherwise, return the index where it would be inserted to keep the array sorted.

Why this is worth learning

Search for a boundary, not a lucky equal element. The desired index is the first position whose value is at least target, which also handles missing targets and duplicates consistently.

Before coding: one-minute experiment

For [1,3,3,7] and target 3, what is the insertion index? Why is returning the first equal midpoint insufficient?

Function signature

func SearchInsert(nums []int, target int) int

Inputs / outputs

• nums: nondecreasing integer array; duplicates are allowed.
• target: value to insert/search.
• Return: the first index whose value is at least target, or len(nums) if none exists.

Example

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

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

Constraints

• 1 <= len(nums) <= 10_000

Core idea (near-solution)

A linear scan can return the first value at least target. Sortedness lets one inspection certify many positions: a value below target rules out itself and every earlier value, while a qualifying value rules out every later position as an earlier boundary. This derives the lower-bound predicate. Equality cannot return immediately when duplicates exist, because an earlier equal value may still be the required answer.

Use lower-bound binary search to find the first index where nums[i] >= target.

Invariant: all elements before lo are < target; all elements at or after hi are >= target.

Algorithm (step-by-step)

1. Set lo = 0, hi = len(nums) (exclusive).
2. While lo < hi:
   • mid = lo + (hi-lo)/2.
   • If nums[mid] < target, set lo = mid + 1.
   • Else set hi = mid.
3. Return lo.

Correctness sketch

Use the half-open search interval [lo,hi). Every index before lo has value less than target, and every index at or after hi has value at least target. Initially both claims hold vacuously. If nums[mid]<target, sortedness proves all positions through mid are too small, so lo=mid+1 preserves the partition. Otherwise mid and all later positions qualify, so hi=mid preserves it. Each update strictly shrinks the interval. At lo=hi the partition has one boundary, which is the first qualifying index or len(nums) when none qualifies.

Trace (hand walkthrough)

Use nums=[1,3,5,6] and the half-open interval [lo,hi).

Target	lo	hi	mid / value	Update
5	0	4	2 / 5	hi=2; equality keeps searching left
5	0	2	1 / 3	lo=2; stop and return 2
2	0	4	2 / 5	hi=2
2	0	2	1 / 3	hi=1
2	0	1	0 / 1	lo=1; stop and return 1

No branch returns merely because it sees equality. With duplicate 5s, that discipline locates the first one.

Pitfalls to avoid

• Using an inclusive hi and returning the wrong boundary.
• Forgetting that the insertion index can be len(nums).

Debugging lens

Test target below all values, above all values, and repeated equal values. Keep hi exclusive; mixing an inclusive-loop condition with this update scheme can index len(nums).

Complexity

• Time: O(log n).
• Extra space: O(1).

Implementation notes (Go)

• This is a standard lower-bound implementation.

Reconstruction checkpoint

For [1,3,3,7] and target 3, what is the insertion index? Why is returning the first equal midpoint insufficient?

Model answer

The index is 1, the first 3. An equal midpoint might be the second 3 and would not satisfy the lower-bound contract. Continue searching the left boundary by setting hi=mid.

Return to Binary Search · Module quiz