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
C# needs a compiler and Drill does not host one yet, so this page is the reference rather than an exercise: the problem, worked examples, and the solution in full. To type it out, the same problem runs in Python.
Where you start
public int CountInBand(List<int> readings, int low, int high) {
}Worked examples
| Call | Result |
|---|---|
CountInBand(new List<int> { 1, 3, 5, 7, 9 }, 3, 7) | 3 |
CountInBand(new List<int> { 1, 3, 5, 7, 9 }, 4, 4) | 0 |
CountInBand(new List<int> { 2, 2, 2, 2 }, 2, 2) | 4 |
CountInBand(new List<int> { 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 C#
public int CountInBand(List<int> readings, int low, int high) {
if (low > high) return 0;
var bounds = new int[2];
var targets = new int[] { low, high + 1 };
for (int t = 0; t < 2; t++) {
int lo = 0, hi = readings.Count;
while (lo < hi) {
int mid = (lo + hi) / 2;
if (readings[mid] < targets[t]) lo = mid + 1;
else hi = mid;
}
bounds[t] = lo;
}
return bounds[1] - bounds[0];
}