A hiking trail's elevation profile is stored remotely as a list heights that climbs strictly, reaches one summit, then descends strictly: there is an index p with 0 < p < len - 1 such that
heights[0] < heights[1] < ... < heights[p], andheights[p] > heights[p + 1] > ... > heights[len - 1].
You can't see the list. You get a reader object with two methods:
reader.length()returns the number of points (free);reader.get(i)returnsheights[i], and costs one read.
Write find_elevation(target: int, reader) -> int that returns the smallest index i with heights[i] == target, or -1 if the trail never has that elevation.
# heights = [1, 4, 8, 10, 7, 4, 2]
find_elevation(4, reader) # 1 (index 5 also has 4, but 1 is smaller)
find_elevation(7, reader) # 4 (only on the way down)
find_elevation(10, reader) # 3 (the summit)
find_elevation(5, reader) # -1
3 <= reader.length() <= 10^6; heights are in[0, 10^9].- Read budget: at most 100 calls to
reader.getper search, whatever the trail and target. Going over, or asking for an index outside0 .. length - 1, raises an error. Reading every point costs up to a million reads; aim for O(log n) reads.
Show hint
each side of the summit is sorted on its own, so the job splits into three searches. The first finds the summit: comparing get(i) with get(i + 1) tells you whether i is on the way up or the way down. Search the climbing side first, since it holds the smaller indexes.