How many readings fall in the band
A sorted column of measurements is checked against a tolerance band, and the report wants the count inside it — over millions of rows, so scanning is out.
- The readings arrive sorted ascending.
- Both ends of the band are inclusive.
- A band that runs backwards contains nothing.
- Return how many readings fall inside.
count_in_band(readings: list<int>, low: int, high: int) → int
Where you start
def count_in_band(readings: list[int], low: int, high: int) -> int:
Worked examples
| Call | Result |
|---|---|
count_in_band([1, 3, 5, 7, 9], 3, 7) | 3 |
count_in_band([1, 3, 5, 7, 9], 4, 4) | 0 |
count_in_band([2, 2, 2, 2], 2, 2) | 4 |
count_in_band([1, 2, 3], 3, 1) | 0 |
Hint
Two binary searches: the first position not below the low end, and the first position above the high end. The gap between them is the answer.
Reference solution in Python
def count_in_band(readings: list[int], low: int, high: int) -> int:
if low > high:
return 0
def lower_bound(target):
lo, hi = 0, len(readings)
while lo < hi:
mid = (lo + hi) // 2
if readings[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
return lower_bound(high + 1) - lower_bound(low)