DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Search Insert Position

easyBinary search

Problem statement

You get a sorted array nums of distinct integers and a target. If target is in the array, return its index. If it is not, return the index where it would have to be inserted to keep the array sorted.

Aim for O(log n) time.

Examples

Example 1

Input: nums = [3, 8, 12, 20], target = 12

Output: 2

Explanation: 12 is already at index 2.

Example 2

Input: nums = [3, 8, 12, 20], target = 15

Output: 3

Explanation: 15 belongs between 12 and 20, so it would go at index 3.

Hints

Approach

Binary-search for the lower bound: the first index whose value is >= target.

  1. Set lo = 0 and hi = len(nums). The answer is always inside [lo, hi], and hi may be one past the end.
  2. While lo < hi:
    • mid = lo + (hi - lo) // 2;
    • if nums[mid] < target, the answer is to the right of mid: lo = mid + 1;
    • otherwise mid could be the answer, so keep it: hi = mid.
  3. When lo == hi, that single position is the answer.

The loop never needs a separate "found it" check: an exact match is just a lower bound that happens to hold the target.

ComplexityTime O(log n)Space O(1)
Python
class Solution:
def searchInsert(self, nums: list[int], target: int) -> int:
lo, hi = 0, len(nums)
while lo < hi:
mid = lo + (hi - lo) // 2
if nums[mid] < target:
lo = mid + 1
else:
hi = mid
return lo

Follow-up questions

  • Return the insertion point that goes after any equal elements (the upper bound) when duplicates are allowed.

Frequently asked questions

Python's bisect.bisect_left(nums, target) returns exactly this index. In Java, Arrays.binarySearch returns -(insertionPoint) - 1 when the key is missing, so you have to decode it. Interviewers usually want the loop written by hand first.

Lower bound is the workhorse of time-series lookups: finding where a timestamp falls in sorted metrics, which log segment covers a given time, or which bucket boundary a latency value lands in for a histogram.

With lo < hi, mid is always strictly less than hi, so hi = mid still shrinks the range. The lo = mid + 1 branch shrinks it from the other side.