Coding interview problems › Binary Search

🔍 Binary Search Easy

Search Insert Position

Search Insert Position explained: use binary search to find the lower bound, where a value sits or should be inserted, with tested Python and a live visual.

Also searched as: lower bound binary search · find insertion index in sorted array · bisect_left

🔍

Try it live Free

Binary Search

Search for a value that is not in the array and watch where the range collapses: the final position is the insertion point, and the lab's off-by-one traps show why the bounds matter.

Open the playground →

The problem

Given a sorted list of distinct integers and a target, return the index of the target if it is present. If it is not, return the index where it would be inserted to keep the list sorted. Do it in O(log n).

Inputnums = [1, 3, 5, 6], target = 5
Output2
Inputnums = [1, 3, 5, 6], target = 2
Output1

2 belongs between 1 and 3.

The key insight

The answer is the first index whose value is at least the target, often called the lower bound. Binary search can find that boundary directly: every element left of it is smaller than the target and every element from it onwards is not. When the loop ends, lo lands exactly on that boundary.

Brute force first: Walking from the left until you meet a value that is at least the target works but takes O(n) time.

Step-by-step approach

  1. Set lo = 0 and hi = len(nums). Note that hi is one past the end, because the answer can be len(nums).
  2. While lo < hi, take mid = (lo + hi) // 2.
  3. If nums[mid] < target, the boundary is to the right of mid: set lo = mid + 1.
  4. Otherwise mid could be the boundary itself: set hi = mid.
  5. When lo == hi, return lo.

Python solution

PYTHON 3tested
def search_insert(nums, target):
    lo, hi = 0, len(nums)           # answer lies in [0, len(nums)]
    while lo < hi:
        mid = (lo + hi) // 2
        if nums[mid] < target:
            lo = mid + 1            # boundary is strictly right of mid
        else:
            hi = mid                # mid may be the boundary
    return lo

Complexity

TimeO(log n)
SpaceO(1)

The half-open range [lo, hi) shrinks by about half every iteration and never loses the boundary, so the loop runs O(log n) times with two indices of storage.

Common mistakes

Frequently asked questions

What is the time and space complexity of Search Insert Position?

Binary search for the lower bound takes O(log n) time and O(1) extra space.

Is this the same as bisect_left?

Yes. Python's bisect.bisect_left(nums, target) returns exactly this index, so it is a quick way to check your own implementation.

What changes if the list has duplicates?

The lower-bound loop still works and returns the first index of the target. If you instead want the position after all copies, change the comparison to nums[mid] <= target, which gives the upper bound.

Why does lo end up on the right answer?

The loop keeps the invariant that everything before lo is smaller than target and everything from hi onward is at least target. When lo meets hi, that meeting point is the boundary.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Binary Search Binary Search lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.