Find First and Last Position of Element in Sorted Array

Medium#34both edges

You get an array sorted in non-decreasing order, so equal numbers stand together, and a target. Return the first and the last index of the target, or [−1, −1] if it is not there, in O(log n) time. Our example: [1, 3, 3, 3, 3, 3, 6, 8] and 3 — the answer is [1, 5].

34 Find First and Last Position of Element in Sorted ArrayWalkthrough · 1×

Example: [1, 3, 3, 3, 3, 3, 6, 8], find the edges of the 3s. Two searches run one after the other; the matches written down stay lit.

0113233343536678
still in the rangemiddle, checked nowthrown awaywritten down: first or last

No 3 found yet: first = last = -1

01/32
restart · back · play · step
Speed
1function searchRange(nums, target):
2 first = -1; last = -1
3 lo = 0; hi = len(nums) - 1
4 while lo <= hi: // search 1: the first target
5 mid = floor((lo + hi) / 2)
6 if nums[mid] < target: lo = mid + 1
7 else:
8 if nums[mid] == target: first = mid
9 hi = mid - 1 // an earlier one may exist
10 lo = 0; hi = len(nums) - 1
11 while lo <= hi: // search 2: the last target
12 mid = floor((lo + hi) / 2)
13 if nums[mid] > target: hi = mid - 1
14 else:
15 if nums[mid] == target: last = mid
16 lo = mid + 1 // a later one may exist
17 return [first, last]
state
first
-1
last
-1
lo
–
hi
–
mid
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Finding one 3 is not enough: the answer is the edges of the block of 3s. So on a match the run writes the index down and keeps going, left in the first search and right in the second.
  2. In the first search everything left of lo is smaller than the target, and everything right of hi is the target or bigger. When lo passes hi, the last match written down is the leftmost one. The second search is its mirror.
  3. Stopping at a match and stepping outwards one by one would take O(n) on an array of nothing but 3s. Two searches take O(log n) whatever the block.

Complexity

Time O(log n): two binary searches, one after the other. Memory O(1).

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.