Search Insert Position
Asked at Google
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| EASY | View all Google 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.
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Search Insert Position?
Search Insert Position is asked at Google. 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.