Search Insert Position
Problem statement
You are given a sorted list of distinct integers, nums, and a target value. If target is already in the list, return its index. If it isn't, return the index where it would sit if you inserted it and kept the list sorted.
Your algorithm has to run in O(log n) time — checking every value one at a time isn't fast enough once the list gets large.
Examples
Example 1
Input: nums = [1, 3, 5, 6], target = 5
Output: 2
Explanation: 5 is already in the list, sitting at index 2.
Example 2
Input: nums = [1, 3, 5, 6], target = 7
Output: 4
Explanation: 7 is bigger than every value in the list, so it belongs right after the last one — at index 4, one past the end.
Hints
Approach
Optimal: Binary search, lower bound
Intuition
This drops the separate res variable. When the loop ends (left > right), left has already walked exactly to the first index holding a value >= target — there's nothing left to track. It's the same idea as Better, just written the way a "lower bound" binary search usually is, which is also what library functions like Python's bisect.bisect_left or C++'s std::lower_bound do under the hood. Fewer variables means fewer places to make an off-by-one mistake, so this is the version worth writing from memory.
Steps
- Set
left = 0,right = len(nums) - 1. - While
left <= right: computemid = (left + right) // 2. - If
nums[mid] == target, returnmid. - If
nums[mid] > target, search left:right = mid - 1. - Otherwise, search right:
left = mid + 1. - Return
left.
Dry run
nums = [1, 3, 5, 6], target = 5
| step | left | right | mid | nums[mid] | action |
|---|---|---|---|---|---|
| 1 | 0 | 3 | 1 | 3 | 3 < 5 → left = 2 |
| 2 | 2 | 3 | 2 | 5 | 5 == 5 → return 2 |
Edge cases: if target is smaller than every value, right keeps shrinking below left while left stays at 0 — the loop ends with left = 0, correctly inserting at the front. An empty list skips the loop entirely and returns left = 0.
Complexity
Time O(log n) - Same halving as Better: the range shrinks to nothing in about log₂(n) steps.
Space O(1) - Only `left`, `right` and `mid`; nothing grows with the input.
class Solution:
def searchInsert(self, nums: list[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[mid] > target:
right = mid - 1
else:
left = mid + 1
return left
if __name__ == "__main__":
print(Solution().searchInsert([1, 3, 5, 6], 5)) # 2
print(Solution().searchInsert([1, 3, 5, 6], 7)) # 4RecapThe whole problem in a few lines, for the night before
- Spot it: "sorted array, distinct values, find the index or where it would go" — a classic lower-bound binary search
- Idea: binary search with
left <= right; when the loop ends,leftis already sitting at the answer - Cost: O(log n) time, O(1) space
- Trap: forgetting the "insert at the end" case — the answer can be
len(nums), one past the last valid index, not-1
Interview follow-ups
What changes if
numscan contain duplicate values?Not much. The lower-bound binary search above doesn't rely on the values being distinct — it finds the first index whose value is
>= target, which is well defined whether or not that value repeats. The only thing to clarify with the interviewer is which position they want whentargetalready appears more than once: this approach always returns the leftmost matching index.The list is too large for memory and lives in a database column, sorted. How would you find the insert position?
Don't pull the whole column into memory. If the column has a B-tree index, a query like counting rows with a value less than
targetuses that index to answer in roughly logarithmic time without a full scan. Without a usable index, you could still binary search across the data by issuing range queries (fetch the value at an offset) instead of loading every row, keeping the number of queries around log₂(n).
Frequently asked questions
That finds target only if it's already there, and it scans the list one value at a time — O(n), and it gives you no answer at all when target is missing. This problem needs both an O(log n) search and a sensible answer for the "not found" case, which is exactly what the binary search versions give you.
The binary search handles it without any special case. As the range narrows, right keeps moving below left while left stays pinned at 0, because every value is bigger than target. When the loop ends, left is still 0 — correctly inserting before everything.
The same shape shows up when you keep a sorted list and need to place something new into it without re-sorting from scratch — for example finding where a new certificate's expiry date belongs in a sorted list of expiries, or which capacity tier a new instance size slots into among a sorted list of thresholds. Binary search keeps that lookup fast as the list grows.
Mentioning it is fine, and it's exactly what this problem is really asking you to build. But most interviewers will ask you to implement the logic by hand right after, so know the pointer version cold — the library call is really the "lower bound" approach with the details hidden.
