Find First and Last Position of Element in Sorted Array
Real-world version: Deviation Value SpanThe statement here is our own: the same inputs, outputs and technique.
A machine shop keeps an archive of how far finished parts drifted from a reference line, measured in tenths of a millimetre. A part on the long side of the line records a positive drift and a part on the short side records a negative one.
The archive readings is filed from smallest drift to largest, never decreasing as you move forward. Any drift may be filed more than once, because different parts can miss the line by the very same amount. Because the filing is ordered, all copies of one drift sit shoulder to shoulder in a single unbroken run.
Given the archive and one drift value, report where that run begins and where it ends: return [first, last], the lowest index holding value and the highest index holding value. When the archive holds no copy of value at all, return [-1, -1] instead.
The archive can grow to a hundred thousand readings and may also be completely empty. Each answer has to be produced in time that grows only with the logarithm of the archive size, so stepping through the readings one after another is not fast enough.
Examples
Example 1
- Input
- readings = [-4, -1, -1, -1, 3, 7], value = -1
- Output
- [1, 3]
Three parts drifted -1 tenths and they occupy indices 1, 2 and 3. Index 0 holds a smaller drift and index 4 already holds a larger one.
Example 2
- Input
- readings = [-4, -1, 3], value = 5
- Output
- [-1, -1]
A drift of 5 would belong between 3 and the end of the archive, but no part actually recorded it, so the absent marker is returned.
Example 3
- Input
- readings = [2, 2, 2], value = 2
- Output
- [0, 2]
Every filed part drifted the same amount, so the run stretches from the first index to the last.
Constraints
- 0 <= readings.length <= 10^5
- -10^9 <= readings[i] <= 10^9
- readings is filed in non-decreasing order
- -10^9 <= value <= 10^9
- The lookup must run in O(log n) time
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def value_span(readings: list[int], value: int) -> list[int]:public int[] valueSpan(int[] readings, int value)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 15 test cases: 15 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's