Search Insert Position
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Return the index of the target in a sorted list, or the index where it would be inserted to keep the order.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1If the target is missing, the answer is where the first bigger value sits.
- Hint 2Think of the list as a row of "too small, too small, ... not too small, not too small". You want the first "not too small".
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
You bought a new book and want to slot it into your shelf, which is sorted by title. You do not slide along from the left. You look at the book in the middle: should mine go before or after? Keep halving until you find the first book that should come after (or equal) yours. That gap is where yours goes.
- The obvious way
Scan until a value is not smaller than the target: O(n).
- The key insight
Every item is either "too small" (before the target) or "not too small", and all the too-small ones come first. Binary search for the first not-too-small one: if the middle is not too small the answer is the middle or something earlier; if it is too small the answer is later. The answer may even be the end of the list.
- The algorithm
- Left marker at the first item, right marker one past the last item.
- Look at the middle. Not smaller than the target? The answer is here or earlier: right marker = middle.
- Smaller than the target? The answer is later: left marker = middle + 1.
- When the markers meet, that position is the answer.
Watch it run
Examplenumbers = [1, 3, 5, 6], target = 2
Middle is 5. Not smaller than 2, so 2 belongs here or earlier. Throw away 5 and 6.
possible places: before 5
Where people slip
- The right marker starts one past the end, because the answer can be the length of the list.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def search_insert(nums, target):
low, high = 0, len(nums) # high = len allows "insert at the end"
while low < high:
middle = (low + high) // 2
if nums[middle] >= target:
high = middle # answer is here or earlier
else:
low = middle + 1 # answer is later
return lowNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.