35. Search Insert Position
Asked at Google, Bloomberg
Difficulty
Easy
Time
O(log n)
Space
O(1)
Pattern
Array
Companies
2
Problem
You are given a sorted array of distinct integers nums, and a target value. If target is already in the array, return its index. If it is not there, return the index where it should be inserted so the array stays sorted.
Because the array is sorted, you can find that position without looking at every element. Your algorithm must run in O(log n) time, which means binary search.
Think of the answer as the first index i where nums[i] >= target. If every element is smaller than target, the answer is nums.length (the target goes at the end).
Find the first slot that is not smaller
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
nums = [1,3,5,6], target = 52nums = [1,3,5,6], target = 21nums = [1,3,5,6], target = 74Asked At
2 companies| Company | Difficulty | |
|---|---|---|
| Easy | View all Google questions → | |
| Bloomberg | Easy | View all Bloomberg questions → |
How to Think About It
Linear scan: iterate from left to right and return the first index where arr[i] >= target — O(n).
Binary search with explicit checks: search for exact match, then scan neighbors to find insert position.
Lower bound binary search: maintain the invariant that lo is the smallest possible insert position.
Standard binary search template with early return on exact match, adjusting lo/hi to converge on insert point.
Optimal lower-bound: after loop, lo always holds the correct insert index even if target is absent.
Optimal Approach
Use the standard binary search lower-bound pattern. Maintain two pointers lo and hi. In each iteration, compute mid. If arr[mid] equals target, return mid immediately. If arr[mid] is less than target, move lo to mid + 1. Otherwise, move hi to mid - 1. After the loop terminates, lo points to the correct insertion position. This works because lo always tracks the smallest index where arr[lo] >= target.
Binary search for the lower bound
What Trips People Up in Real Interviews
Clarify whether the array can contain duplicates — this changes whether you need lower or upper bound.
Confirm that O(log n) is required; interviewer will reject O(n) solutions.
Walk through an example where target is larger than all elements — insert at end.
Walk through an example where target is smaller than all elements — insert at index 0.
Mention that Python bisect.bisect_left directly solves this, but explain the underlying logic.
Solution Code
O(log n) timedef search_insert(nums, target):
lo, hi = 0, len(nums) - 1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
return mid
elif nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return loFrequently Asked Questions
What is the Search Insert Position 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 inserted in order. The solution must run in O(log n) time complexity using a binary search approach.
How do you solve Search Insert Position?
The optimal approach runs in O(log n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Search Insert Position?
Search Insert Position is asked at Google, Bloomberg. It is a easy difficulty problem.
What are common mistakes on Search Insert Position?
- Clarify whether the array can contain duplicates — this changes whether you need lower or upper bound.
- Confirm that O(log n) is required; interviewer will reject O(n) solutions.
- Walk through an example where target is larger than all elements — insert at end.
- Walk through an example where target is smaller than all elements — insert at index 0.
- Mention that Python bisect.bisect_left directly solves this, but explain the underlying logic.