Lower bound and upper bound from the library
Python has the lower-bound search built in. bisect_left(nums, target) from the bisect module returns the first position whose value is at least the target, or len(nums) when there is none. When the bound is one step of a larger solution, this call is shorter than the loop and has no boundary to get wrong. An interviewer who asks for binary search itself still expects the loop, and a search whose condition is not a comparison with a value in the array needs the loop too.
The module has a second function, bisect_right(nums, target). It returns the first position whose value is greater than the target, which is called the upper bound. The two functions give different positions only when the target is in the array.
Here are both bounds for a few targets in the sorted array [5, 7, 7, 8, 8, 10], in which two values occur twice:
| Target | Lower bound | Upper bound | Upper minus lower |
|---|---|---|---|
| 8 | 3 | 5 | 2 |
| 7 | 1 | 3 | 2 |
| 6 | 1 | 1 | 0 |
| 11 | 6 | 6 | 0 |
For a target that is present, the lower bound is the position of its first copy and the upper bound is one past its last copy. For a target that is absent, such as 6 or 11, both bounds are the same position, the one where it would be inserted. Four common questions follow from that, each answered with one or two calls:
- Is the target present? Yes, if the lower bound is a position inside the array and the value there equals the target. The lower bound of 6 is 1, which holds 7, so 6 is absent. The lower bound of 11 is 6, past the end, so there is no value to compare and 11 is absent too.
- How many copies are there? The upper bound minus the lower bound: copies of 8 and copies of 6.
- Where are the first and the last copy? When the target is present, at the lower bound and at one before the upper bound: positions 3 and 4 for the target 8.
- How many values lie between and , both included? The upper bound of minus the lower bound of . From 6 to 9 that is values: 7, 7, 8 and 8.
Find the first and last copy of a value
The third of those questions is a LeetCode problem as it stands:
You get an array nums sorted in non-decreasing order, so values can repeat, and a target. Return the first and last positions of the target as [first, last], or [-1, -1] if it is absent, in time.
Constraints
-
nums[i],target
Sample 1 · Input
nums = [5,7,7,8,8,10], target = 8
Output
[3,4]
Sample 2 · Input
nums = [5,7,7,8,8,10], target = 6
Output
[-1,-1]
Sample 3 · Input
nums = [], target = 0
Output
[-1,-1]
The first sample is the array from the table, and its two 8s are at positions 3 and 4. In the second sample 6 is absent. In the third the array is empty, so every target is absent.
def search_range(nums, target):
first = bisect_left(nums, target)
if first == len(nums) or nums[first] != target:
return [-1, -1]
last = bisect_right(nums, target) - 1
return [first, last]
nums = [5, 7, 7, 8, 8, 10]
print(search_range(nums, 8), search_range(nums, 6), search_range([], 0))The program prints [3, 4] [-1, -1] [-1, -1], the answers to the three samples.
The presence test compares first with the length before it reads nums[first]. The order matters for the empty array, where the lower bound is 0 and there is no position 0 to read.
To write the upper bound yourself, take the first-YES loop and change its question to "is the value at mid greater than the target?". That question is monotone on a sorted array for the same reason as the lower bound's question.
Step through the lower bound of 8
The stepper runs the lower-bound search for 8 on the same array. At each probe you choose which side of mid to keep, and a wrong choice is explained and not applied. When mid lands on an 8, the side to keep is still the left: that 8 is saved, and an earlier copy may be there.
Search a rotated sorted array
Everything so far relied on the whole array being sorted. The rest of this page is about two kinds of array that are not sorted, in which a probe can still tell you which half to keep. The first kind is a sorted array that has been rotated: some values were taken off the front and put at the back, in the same order.
An array of distinct values was sorted in ascending order and then possibly rotated: some values from the front were moved to the back, as [0,1,2,4,5,6,7] becomes [4,5,6,7,0,1,2]. Return the position of target, or -1 if it is absent, in time.
Constraints
-
nums[i],target - All values of
numsare distinct
Sample 1 · Input
nums = [4,5,6,7,0,1,2], target = 0
Output
4
Sample 2 · Input
nums = [4,5,6,7,0,1,2], target = 3
Output
-1
Sample 3 · Input
nums = [1], target = 0
Output
-1
In the first sample the values rise from 4 to 7, drop to 0, and rise again to 2. A rotated array has at most one such drop, and every value before the drop is larger than every value after it.
The lower-bound question is no use here. For the target 1, the answers to "is this value at least 1?" read YES, YES, YES, YES, NO, YES, YES. They change twice, so a NO at one position says nothing about the positions before it.
A probe can use a different fact: cut any range of a rotated array at mid, and at least one of the two pieces is sorted. The range has at most one drop, and the drop can be inside only one of the pieces, positions left to mid or positions mid to right. The other piece has no drop, so its values only rise.
One comparison tells which piece is sorted. A drop between left and mid would make the value at mid smaller than the value at left, because every value after the drop is smaller than every value before it. So if the value at left is at most the value at mid, there is no drop between them and the left piece is sorted. Otherwise the drop is in the left piece, and the right piece is the sorted one.
A sorted piece is easy to test: the target can be in it only if the target lies between the piece's first and last value. If it does, the search keeps that piece. If it does not, the target can only be in the other piece, and the search keeps that one. Either way about half of the range is gone, and the search never has to work out where the drop is.
Here is the first probe of the search for 0 in the first sample. The range is positions 0 to 6 and mid is 3, which holds 7. Since , the left piece [4, 5, 6, 7] is sorted, and 0 is not between 4 and 7, so the search keeps positions 4 to 6.
The second probe is position 5, which holds 1. Since , the left piece [0, 1] is sorted, and 0 is between 0 and 1, so the search keeps position 4 alone. The third probe finds 0 there.
The listing first checks whether mid holds the target. Otherwise mid is ruled out, so each range test leaves the value at mid out with a strict <: the target can be in a sorted left piece when nums[left] <= target < nums[mid], and in a sorted right piece when nums[mid] < target <= nums[right].
def search(nums, target):
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
print(search([4, 5, 6, 7, 0, 1, 2], 0), search([4, 5, 6, 7, 0, 1, 2], 3))The program prints 4 and -1, the answers to the first two samples.
The values are guaranteed to be distinct, and the method needs that. With repeated values, the values at left and mid can be equal while a drop sits between them, and the comparison no longer says which piece is sorted. The mistakes at the end of the page show an array where that goes wrong.
Find a peak by comparing neighbours
The second kind of array is not sorted at all. The problem guarantees only that two neighbouring values are never equal, and it counts the positions just outside the array as .
A peak is a value strictly larger than both of its neighbours, where the positions just outside the array count as . Given an array in which neighbouring values are never equal, return the position of any peak in time.
Constraints
-
nums[i] nums[i] != nums[i + 1]
Sample 1 · Input
nums = [1,2,3,1]
Output
2
Sample 2 · Input
nums = [1,2,1,3,5,6,4]
Output
5
In the first sample the only peak is the 3 at position 2, which is larger than the 2 before it and the 1 after it. The second sample has two peaks, the 2 at position 1 and the 6 at position 5, and either position is accepted. An end value only has to be larger than its one neighbour, because the beyond the end is smaller than any value.
A scan finds a peak in at most comparisons. To get by with about , each probe has to throw away half of the range and still be sure that a peak is in the half it keeps.
The search does that by keeping a range with one property: the values step up into the range at its left end and step down out of it at its right end. That is, the value just before the range is smaller than the range's first value, and the value just after the range is smaller than its last value. The whole array is such a range, because of the on both sides.
A range like that always contains a peak. Start at its first value and walk right for as long as the next value is larger. The walk cannot leave the range, because the value after the range's last value is smaller. So it stops inside the range, at a value whose right neighbour is smaller. Its left neighbour is smaller too: either the walk stepped up from it, or the walk never moved and the left neighbour is the value just before the range. The walk has stopped on a peak.
To halve such a range, compare the value at mid with the value after it:
- If the next value is larger, positions
mid + 1torightare a range with the same property, because the value just before it, atmid, is smaller than its first value. The search keeps that half:left = mid + 1. - If the next value is smaller, positions
lefttomidare such a range, because the value just after it, atmid + 1, is smaller than its last value. The search keeps that half:right = mid.
This loop is built differently from the first-YES loop. It has no target and saves no answer. It shrinks a range that is known to contain a peak until one position is left, and that position is a peak. So it runs while left < right, and it keeps mid in the range with right = mid, because mid may be the peak.
Rounding mid down keeps it below right for as long as left < right, and that does two things. right = mid always shortens the range, so the loop ends. And mid + 1 is a position inside the range, so reading the value there cannot run off the end of the array.
mid is larger, so the range from position 4 to 6 starts with a step up, ends before , and contains a peak.def find_peak_element(nums):
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left) // 2
if nums[mid] < nums[mid + 1]:
left = mid + 1
else:
right = mid
return left
print(find_peak_element([1, 2, 3, 1]), find_peak_element([1, 2, 1, 3, 5, 6, 4]))The program prints 2 and 5, the answers to the two samples.
On the second sample the probes are position 3 (3 is less than 5, so the search keeps positions 4 to 6), position 5 (6 is more than 4, so it keeps positions 4 and 5) and position 4 (5 is less than 6, so it keeps position 5). One position is left, and it holds the peak 6.
How many probes each search takes
- Lower or upper bound
- One call is one binary search. Find First and Last Position allows values, which is at most 17 probes per call and 34 for both ends.
- Rotated search
time, extra space - Each probe keeps one of the two pieces: at most 13 probes for the 5,000 values the problem allows.
- Peak search
time, extra space - Each probe keeps about half of the range: at most 10 probes for the 1,000 values the problem allows.
- Scan from the left
- Up to comparisons for Find First and Last Position.
Common mistakes on sorted and nearly sorted arrays
Reading the value at the lower bound without checking that the lower bound is inside the array.
- Where it breaks
- In
[-1, 0, 3, 5, 9, 12]the lower bound of 13 is 6, one past the last position. Readingnums[6]raisesIndexErrorin Python and is undefined behavior in C++. - The fix
- Compare the lower bound with the length first, as the Find First and Last Position listing does.
Testing
nums[left] < nums[mid]in the rotated search.- Where it breaks
- On
[3, 1]with target 1,leftandmidare both 0, so3 < 3fails and the search takes positionsmidtorightfor the sorted piece. 1 is not above 3, so it setsrightto and returns-1, although 1 is at position 1. - The fix
- Use
<=. Whenleftequalsmid, the left piece is a single value, which is sorted.
Using the rotated search on an array with repeated values.
- Where it breaks
- In
[1, 0, 1, 1, 1]with target 0, the first probe is position 2. The values atleftandmidare both 1, so the search takes[1, 0, 1]for the sorted piece, sees that 0 is not between 1 and 1, and moves to positions 3 and 4. It returns-1, although 0 is at position 1. - The fix
- Use it only when the values are distinct. With repeats no comparison at the probe can locate the drop:
[1, 0, 1, 1, 1]and[1, 1, 1, 0, 1]hold the same values at positions 0, 2 and 4.
Pairing
right = midwithwhile left <= right.- Where it breaks
- In the peak search on
[1, 2, 3, 1], the range shrinks to position 2 alone. Thenmidis 2,right = midchanges nothing, and the loop never ends. - The fix
- Pair
right = midwithwhile left < right, andright = mid - 1withwhile left <= right.
Recall In the peak search, what goes wrong if a smaller next value leads to `right = mid - 1` instead of `right = mid`?
The peak can be at mid, and mid - 1 puts it outside the range. On [1, 3, 2] the first probe is position 1: 3 is more than 2, so a peak lies in positions 0 to 1. With right = mid - 1 the range becomes position 0 alone, and the search returns 0, where the value 1 is smaller than its neighbour 3.
Recall What are the lower bound and the upper bound of 2 in `[1, 2, 2, 2, 5]`? And of 3?
For 2 they are 1 and 4: the copies are at positions 1 to 3, and of them. For 3 both bounds are 4, the position of the 5, because 3 is absent and would be inserted there.