The beacons that are missing

Problem

Nicanor sets the beacons that mark the navigable channel of the river, numbered from 1 going downstream. The list of the ones already in place arrives sorted from smallest to largest and with no repeats, but with holes: there are numbers that were never set.

Nicanor is going to order iron for a single one, and he tells you which one he wants: the k-th missing one, counting the holes from smallest to largest starting at number 1.

You get the list of beacons already in place and the number k, and you return the number of that beacon. With 2, 3, 4, 7 and 11 in place, the missing numbers are 1, 5, 6, 8, 9, 10, 12 and so on, so the fifth missing one is 9.

The numbers don't stop where the list ends, because the river goes on: every number larger than the last beacon in place is a hole too, and it counts too. With 1, 2 and 3 in place nothing is missing between them, so the holes are 4, 5, 6 and so on, and the second missing one is 5. If no beacon is in place at all, the k-th missing one is k.

k is always 1 or more. Some stretches of the river have up to 60 beacons in place.

Idea: stand on any row of the list and work out how many numbers are missing before it. If beacon 11 is there and it is the fifth one in place, then 6 numbers are missing between 1 and 11. That count never goes down as you move along the list, so you can split the list in halves and look for the first row where the count has already reached k. That row tells you how many beacons in place are left before your hole, and the number comes out of that: from 1 up to your hole every number is either a beacon in place or a hole, and you already know how many there are of each.

Examples

• The example

  [2, 3, 4, 7, 11], 5 → 9

• No holes, the next one

  [1, 2, 3], 2 → 5

• No beacon in place

  [], 3 → 3

• The first free one is 1

  [2], 1 → 1

• All in a row from 1

  [1, 2, 3], 1 → 4

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

You start with this

def free_beacon(placed, k):
    pass

function freeBeacon(placed, k) {
}