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.

Sitelet https://gitgood.dev/coding/search-insert-position

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.

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.