Problems › JavaScript › patterns
The smallest reading in a wrapped log
A ring buffer holds readings that were written in ascending order but wrapped around at some point. The oldest reading is the smallest one, and finding it should not cost a full scan.
- The readings were ascending before being rotated some number of places.
- All the values are distinct.
- A buffer that was not rotated at all is still valid input.
- An empty buffer has no smallest reading: return 0.
oldestReading(readings: list<int>) → int
Where you start
function oldestReading(readings) {
}Worked examples
| Call | Result |
|---|---|
oldestReading([4,5,6,7,0,1,2]) | 0 |
oldestReading([1,2,3]) | 1 |
oldestReading([3,1,2]) | 1 |
oldestReading([2,3,4,5,1]) | 1 |
Hint
Compare the middle with the last entry. If the middle is larger, the wrap is to its right; otherwise the answer is the middle or to its left.
Reference solution in JavaScript
function oldestReading(readings) {
if (readings.length === 0) return 0;
let lo = 0;
let hi = readings.length - 1;
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2);
if (readings[mid] > readings[hi]) lo = mid + 1;
else hi = mid;
}
return readings[lo];
}