Find First and Last Position of Element in Sorted Array
You get a list of integers nums sorted in non-decreasing order, so a value can repeat, and an integer target. Return a list of two indexes, counting from 0: the first and the last position where target appears. If target is not in the list, return [-1, -1]. Aim for O(log n) time.
Function
- numsinteger-array
- the sorted list of integers, which may repeat values
- targetinteger
- the value to look for
- Returnsinteger-array
- the first and the last index of target, or [-1, -1] if it is missing
Constraints
1 ≤ nums.length ≤ 104-104 ≤ nums[i], target ≤ 104numsis sorted in non-decreasing order.
Examples
- Input
- nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 5
- Output
- [1, 3]
- Explanation
- The three copies of 5 sit at indexes 1, 2 and 3, so the run starts at 1 and ends at 3. Index 0 holds 3 and index 4 holds 8, so the run cannot reach further.
- Input
- nums = [3, 5, 5, 5, 8, 9, 9, 12]target = 7
- Output
- [-1, -1]
- Explanation
- 7 would sit between 5 at index 3 and 8 at index 4, and neither is 7. The list holds no copy, so the answer is
[-1, -1].
Follow-up
If the same list gets thousands of queries for different targets, can one pass over it in advance make each query faster than O(log n)?
Hints
Open them one at a time. Each one gives away a little more.
Because
numsis sorted, all copies oftargetsit next to each other in one run. You need the two ends of that run.Finding one copy and walking outward can cost
O(n)when the run is long. Instead, change the binary search so it keeps going left after a match: it then stops on the first index whose value is at least the number you search for.Write one helper that returns the first index with
nums[i] ≥ value. Call it withtargetto get the start of the run, check that the value there istarget, and call it withtarget + 1: the run ends one index before that.
Solution
A plain binary search stops at whichever copy of target it meets, and that copy can be anywhere in the run. Search for a lower bound instead: the first index whose value is at least a given number. The lower bounds of target and target + 1 give both ends of the run in O(log n).
Scan the whole list
Intuition
Walk the list once. The first index that holds target is the start and the last one is the end. If target never appears, both stay -1.
This works on any list, sorted or not, and that is its weakness: it reads all n values. A list of 10^4 values costs 10,000 comparisons where about 28 would do.
Algorithm
- Set
first = last = -1. - For each index
i, ifnums[i]equalstarget, setfirst = iwhenfirstis still-1, and setlast = i. - Return
[first, last].
def searchRange(nums, target):
first = last = -1
for i, value in enumerate(nums):
if value == target:
if first == -1:
first = i # the first match fixes the start
last = i # every later match moves the end
return [first, last]Find one copy, then expand
Intuition
Binary search for any index that holds target. The list is sorted, so every copy sits in one unbroken run around that index: step left and right while the neighbour is still target.
The search costs O(log n) and the walk one step per copy, k in all. When most of the list is target, say 10^4 copies, the walk reads every value and you are back to a linear scan.
Algorithm
- Binary search for any index
foundwithnums[found] == target. - If there is none, return
[-1, -1]. - Move
firstleft fromfoundwhile the value before it equalstarget. - Move
lastright fromfoundwhile the value after it equalstarget. - Return
[first, last].
def searchRange(nums, target):
# An ordinary binary search finds some copy of target, if there is one.
lo, hi = 0, len(nums) - 1
found = -1
while lo <= hi:
mid = (lo + hi) // 2
if nums[mid] == target:
found = mid
break
if nums[mid] < target:
lo = mid + 1
else:
hi = mid - 1
if found == -1:
return [-1, -1]
# The copies sit next to each other, so walk out to both ends of the run.
first = last = found
while first > 0 and nums[first - 1] == target:
first -= 1
while last < len(nums) - 1 and nums[last + 1] == target:
last += 1
return [first, last]Two lower-bound binary searches
Intuition
Ask a different question: what is the first index whose value is at least value? That index is the lower bound, or n if no value qualifies. Keep a half-open range [lo, hi) that always contains it. If nums[mid] < value, then mid and everything before it is too small. Otherwise mid qualifies, but an earlier index might too, so mid stays in range as the new hi. The loop never stops early on a match.
The lower bound of target is where its run starts. The values are integers, so the first value greater than target sits at the lower bound of target + 1, and the run ends one index before it. In the first example the lower bound of 5 is 1 and the lower bound of 6 is 4, where 8 sits: the run is [1, 3]. The two searches take about 28 steps for 10^4 values, whatever the run length.
Algorithm
- Write
lowerBound(value): start withlo = 0,hi = n; whilelo < hi, ifnums[mid] < valuesetlo = mid + 1, else sethi = mid; returnlo. - Set
first = lowerBound(target). - If
first == nornums[first] != target, return[-1, -1]. - Set
last = lowerBound(target + 1) - 1and return[first, last].
def lowerBound(nums, value):
# The first index whose number is at least value, or len(nums) if none is.
lo, hi = 0, len(nums)
while lo < hi:
mid = (lo + hi) // 2
if nums[mid] < value:
lo = mid + 1 # nums[mid] and everything before it is too small
else:
hi = mid # nums[mid] qualifies, but an earlier index might too
return lo
def searchRange(nums, target):
first = lowerBound(nums, target)
if first == len(nums) or nums[first] != target:
return [-1, -1]
# The run of target ends right before the first number above target.
last = lowerBound(nums, target + 1) - 1
return [first, last]
Pitfalls and edge cases
- Returning as soon as
nums[mid] == target. That index can be anywhere in the run: in[3, 5, 5, 5, 8]the first middle is index 2, which is neither end. - Writing
hi = mid - 1in the lower-bound search whennums[mid] ≥ value. That throws awaymid, which may be the answer. - Reading
nums[first]without checkingfirst < n. Whentargetis larger than every value, as 13 would be in the examples, the lower bound isn, one past the end. - Forgetting the shift in Lua and R. Their lists start at 1, so subtract 1 from both positions.
Frequently asked questions3
What is the time complexity of finding the first and last position?
O(log n) time and O(1) space, with two binary searches. Neither stops on a match, so the cost does not depend on how many copies of the target there are: about 14 steps per search for 10^4 values.
What is a lower bound in binary search?
The lower bound of a value is the first index whose element is at least that value, or the length of the list if there is none. It is where the value would be inserted to keep the list sorted. The upper bound is the first index whose element is strictly greater.
Can one binary search function find both the first and the last index?
Yes. Give the search a flag: on a match, record the index and keep searching left for the first copy, or right for the last. Calling a lower-bound search on target and on target + 1 works too. Both run in O(log n).
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def searchRange(nums, target):
# Write code hereTest #1
Test #2
Arguments
nums = [3, 5, 5, 5, 8, 9, 9, 12] target = 5
Expected Output
[1, 3]