How do you approach Search Insert Position?

This is binary search where a miss returns a position rather than -1.

What is the time complexity of Search Insert Position?

Time complexity: O(log n). Space complexity: O(1).

What are common mistakes on Search Insert Position?

Computing the midpoint as (low + high) / 2. In a fixed-width integer language that overflows on large ranges; low + (high - low) / 2 does not. An update that fails to shrink the range, which spins forever on a two-element window. Answering "does it exist" when the question asked for the first or last occurrence - the boundary variants need a different post-loop return.

gitGood.dev

← Back to problems

Search Insert Position

EasyAlgorithms

Description

Given a **sorted** array of distinct integers and a target value, return the index of the target if it is found. If not, return the index where it **would be inserted** to keep the array sorted. You must write an algorithm with O(log n) runtime.

Example 1

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

Output: 2

Example 2

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

Output: 1

Example 3

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

Output: 4

Constraints

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

Search Insert Position: approach, complexity and pitfalls

An easy binary search problem, graded against 6 test cases (3 of them hidden).

The pattern: Binary Search

Halving a search space each step - on sorted arrays, and on answers themselves.

Reach for it when you see: A sorted input, or a monotonic "is this value feasible?" predicate you can binary search over.

More Binary Searchproblems →

If you are stuck

Show the 3-step hint ladder

This is binary search where a miss returns a position rather than -1.
Use the half-open form: lo = 0, hi = nums.length, and narrow until lo === hi.
When the loop ends, lo IS the insertion point - no special handling for 'not found', and it naturally handles inserting past the end.

The optimal approach

Show the approach: Binary search that returns a boundary, not a hit

The insight is that a failed binary search already knows where the value belongs - the standard version just throws that away by returning -1. Written as a lower-bound search, the final position is the answer whether the target was present or not.

Use the half-open form: `lo = 0`, `hi = nums.length` (one past the end), and loop while `lo < hi`, moving `lo = mid + 1` when `nums[mid] < target` and `hi = mid` otherwise. When they meet, `lo` is the first index whose value is not less than the target - which is the target's index if present, and its insertion point if not. There is no separate found/not-found branch at all.

The half-open convention is what makes the edge cases disappear: inserting past the end returns `nums.length` without a special case, and `hi = mid` rather than `mid - 1` avoids skipping the candidate.

One habit worth carrying: compute `mid` as `lo + ((hi - lo) >> 1)` rather than `(lo + hi) / 2`, which overflows in fixed-width integer languages - a famous bug that sat in the JDK's binary search for years.

Time: O(log n)
Space: O(1)

The full reference solution in every supported language stays in the editor above - reveal it there once you have had a real attempt.

What the tests check

Read off this problem's own test suite, so these are the cases a submission actually has to survive.

Single element. A one-element case is included. Two-pointer and window solutions frequently return the wrong thing when the two indices start out equal.
Zero. Zero appears in the input, which is the value most likely to break a truthiness check used in place of an explicit comparison.

Common Binary Search mistakes

These apply to the pattern as a whole, not just this problem.

Computing the midpoint as `(low + high) / 2`. In a fixed-width integer language that overflows on large ranges; `low + (high - low) / 2` does not.
An update that fails to shrink the range, which spins forever on a two-element window.
Answering "does it exist" when the question asked for the first or last occurrence - the boundary variants need a different post-loop return.