Arrays and searching 0/120

Binary search · 2 of 3

Sorted arrays

Use the library's lower and upper bound for membership, counts and runs of equal values, then halve a rotated array and an array with peaks, which are not sorted.

2,752 words · 13 min read

Part 1 of 6 Lower and upper bound

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:

Lower and upper bounds in [5, 7, 7, 8, 8, 10]
TargetLower boundUpper boundUpper minus lower
8352
7132
6110
11660

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: 5−3=25 - 3 = 2 copies of 8 and 1−1=01 - 1 = 0 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 aa and bb, both included? The upper bound of bb minus the lower bound of aa. From 6 to 9 that is 5−1=45 - 1 = 4 values: 7, 7, 8 and 8.