ThyncLabsThyncLabs

Search Insert Position

easy

You are given a sorted array nums of distinct integers and a value target.

Return the index of target if it is present in nums. If it is not, return the index where it would be inserted to keep the array sorted.

Your algorithm must run in O(log n) time.

Hints

The array is sorted. What does sorted data let you throw away with a single comparison?
Found and not-found are secretly the same question: what is the first index whose value is at least the target?
Binary search on the half-open window [lo, n): if nums[mid] < target move lo past mid, otherwise shrink hi to mid. When the window closes, lo is the answer — including lo = n for insert-at-end.

Common doubts

Because n itself is a valid answer — if target is larger than every element, it inserts at the end. Starting hi = n - 1 makes that index unreachable. The window [lo, hi) is half-open: hi is a candidate answer, not a candidate array index to read.
The loop finds the first index i with nums[i] >= target. If target exists (values are distinct), that first >= is an exact match, so i is its index. If it does not exist, i is precisely the gap where it belongs. No separate branches needed.
When nums[mid] >= target, index mid might itself be the answer — the first such index. hi = mid keeps it inside the window; hi = mid - 1 could discard the correct answer and return an index one too far left.
No. Each iteration either moves lo up (lo = mid + 1) or moves hi down to mid, and since mid < hi always holds inside the loop, the window hi - lo strictly shrinks every step until it hits zero.

Interview follow-ups

Nothing — this exact loop already computes the leftmost index with nums[i] >= target (the lower bound). That robustness is why the nums[mid] < target comparison, not <=, is the version worth memorizing.
Run this lower-bound search twice: once for target (first occurrence) and once for target + 1, then subtract one from that result (last occurrence). If the two bounds are equal, the target is absent.
Yes — this function is exactly Python's bisect.bisect_left, C++'s std::lower_bound, and Go's sort.SearchInts. Interviewers usually want the loop written by hand once, then are happy to see you know the standard-library name for it.
Binary search still works, but each step must first decide which half of the window is sorted, then check whether the target lies inside that sorted half — that is the Search in Rotated Sorted Array pattern.

Fun facts

  • This problem is the standard library in disguise: Python ships it as bisect.bisect_left, C++ as std::lower_bound, and Go as sort.SearchInts — you are re-implementing one of the most-called functions in computing.
  • Binary search's halving is brutal in the best way: a sorted array of ten thousand elements needs at most 14 comparisons, and a billion elements only about 30.
  • Jon Bentley reported that when he asked professional programmers to write binary search, roughly 90% got it wrong on the first try — almost always at the boundaries this problem forces you to get right.
  • The lower-bound window trick here powers a whole family of harder problems: first and last occurrence, finding the peak, and binary searching on the answer itself (like minimum capacity to ship packages).

Asked at

AmazonMicrosoftGoogleAppleAdobeBloomberg
Frequently Sometimes Occasionally
Example 1
Input: nums = [1,3,5,6], target = 5
Output: 2
`5` is already in the array at index `2`.
Example 2
Input: nums = [1,3,5,6], target = 2
Output: 1
`2` is not present. It would slot in between `1` and `3` — at index `1`.
Example 3
Input: nums = [1,3,5,6], target = 7
Output: 4
`7` is larger than everything, so it goes at the end — index `4`.
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

Solve this problem →