The nearest stop

Problem

Maya teaches diving and keeps the table of stops taped to her suit: the depths in meters where you have to hold and wait, sorted from the shallowest to the deepest. On the way up she checks her gauge, which can read any depth at all, and she has to decide which stop on the table it is closest to.

Write a function that takes the table sorted from smallest to largest and the gauge reading, and returns the depth of the nearest stop. Not the position: the depth. With the table 3, 6, 9, 12 and 21 and a reading of 10 you return 9, because from 10 to 9 there is one meter and from 10 to 12 there are two.

If the reading is the same distance from two stops, the shallower one wins: with the table 4 and 8 and a reading of 6 you return 4.

If the reading lands exactly on a stop, the nearest one is that same stop: with that first table, a reading of 12 returns 12.

If the reading is shallower than the shallowest stop, you return that one, and if it is deeper than the deepest one, you return that one: with that same table, a reading of 1 returns 3 and a reading of 40 returns 21.

If the table arrives empty, you return -1.

You cannot use min or Math.min, and you cannot sort the table again: the whole point of the challenge is not to walk the whole thing.

Idea: search by halves for the place where the reading would fit. Once you have it, the nearest stop can only be one of the two left on either side of that cut, so comparing those two is enough.

Examples

• The gauge reading

  [3, 6, 9, 12, 21], 10 → 9

• Closer to the next one

  [3, 6, 9, 12, 21], 11 → 12

• A tie, and the shallower one wins

  [4, 8], 6 → 4

• Right on a stop

  [3, 6, 9, 12, 21], 12 → 12

• Shallower than all of them

  [3, 6, 9, 12, 21], 1 → 3

• Deeper than all of them

  [3, 6, 9, 12, 21], 40 → 21

Besides these, the challenge has hidden tests that are revealed when you submit your solution.

You start with this

def nearest_stop(table, reading):
    pass

function nearestStop(table, reading) {
}