Skip to main content

35. Search Insert Position

easy

Find the index where a target would be inserted in a sorted array. The classic 'lower bound' problem — once you internalize it, half of binary search becomes muscle memory.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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

Constraints

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums contains distinct values sorted in ascending order.
  • -10^4 <= target <= 10^4

Examples

Example 1

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

Example 2

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

Explanation: 2 would be inserted between 1 and 3, at index 1.

Example 3

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

Explanation: 7 is larger than all elements, so it goes at the end.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

This is just plain binary search with one twist: when you don't find the target, you still have to return something useful.

Hint 2

Use the half-open invariant: lo and hi bracket the candidate insertion index, with hi = n initially (one past the last index).

Hint 3

After the loop terminates with lo == hi, that value is exactly the lower-bound insertion index.

Solution approach

Reveal approach

Use a lower-bound binary search. Initialize lo = 0 and hi = n (note: one past the last valid index — half-open interval). While lo < hi, compute mid = lo + (hi - lo) / 2. If nums[mid] < target, set lo = mid + 1 (target must go to the right of mid). Otherwise set hi = mid (mid itself is still a candidate). When the loop exits, lo == hi and that value is the insertion index. The invariant: everything left of lo is strictly less than target, and everything at hi or beyond is >= target. This template generalizes to lower_bound / upper_bound problems, and once you internalize the half-open variant you stop fighting off-by-one bugs.

Complexity

Time
O(log n)
Space
O(1)

Related patterns

  • binary-search
  • modified-binary-search

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Microsoft
  • Apple
  • Bloomberg

More Binary Search practice problems

See all Binary Search problems →