Search Insert Position

Easy#35find a number

You get a sorted array of distinct numbers and a target. Return the index of the target if it is there; if not, the index where it would go so the array stays sorted. It has to take O(log n) time. Our example: [1, 4, 6, 9, 13, 17] and 10 — the answer is 4: 10 goes between 9 and 13.

35 Search Insert PositionWalkthrough · 1×

Example: [1, 4, 6, 9, 13, 17], where does 10 go? The empty cell 6 is the place after the last number.

011426394135176lo
the place can still be heremiddle, checked nowruled outthe place for 10

lo starts at the first index, 0

01/16
restart · back · play · step
Speed
1function searchInsert(nums, target):
2 lo = 0
3 hi = len(nums) // the target may go after the end
4 while lo < hi:
5 mid = floor((lo + hi) / 2)
6 if nums[mid] < target:
7 lo = mid + 1 // the place is after mid
8 else:
9 hi = mid // mid may be the place: keep it
10 return lo
state
lo
0
hi
–
mid
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The answer is the first index whose number is not less than the target: the target itself if it is there, the next bigger number if not. If every number is smaller, it is the place after the end, so hi starts at len(nums).
  2. If nums[mid] < target, the place is after mid: lo = mid + 1. Otherwise mid may be the place itself, so hi = mid keeps it in the range.
  3. Everything before lo is less than the target, and everything from hi on is not. When lo meets hi, that border is the answer, found or not.

Complexity

Time O(log n): every step halves the range of places. Memory O(1): three indices.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.