Problems › JavaScript › patterns
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.
countInBand(readings: list<int>, low: int, high: int) → int
Where you start
function countInBand(readings, low, high) {
}Worked examples
| Call | Result |
|---|---|
countInBand([1,3,5,7,9], 3, 7) | 3 |
countInBand([1,3,5,7,9], 4, 4) | 0 |
countInBand([2,2,2,2], 2, 2) | 4 |
countInBand([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 JavaScript
function countInBand(readings, low, high) {
if (low > high) return 0;
const lowerBound = (target) => {
let lo = 0;
let hi = readings.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (readings[mid] < target) lo = mid + 1;
else hi = mid;
}
return lo;
};
return lowerBound(high + 1) - lowerBound(low);
}