The ad with no pair

Problem

Bonifacio runs the booth at the town radio station. Every ad that gets booked goes on the air twice a day, and when he closes the booth he prints the logbook: the number of every ad that went out, sorted from smallest to largest. Today the logbook came out with one row too many, because one ad ended up with a single airing.

You get the logbook and you return the number of that ad. In 3, 3, 7, 7, 9, 12 and 12 the ad with no pair is 9.

The logbook always has an odd number of rows, every other ad shows up exactly twice, and the lone one may be the first or the last. Logbooks go up to 61 rows.

Idea: while the pairs are still complete, the first row of each one falls on an even position, counting from 0: 0 with 1, 2 with 3, 4 with 5. From the lone ad on that breaks and the pairs start on odd positions.

So always compare two at a time, with the pairs just as they come from the start of the logbook: you stand on an even position and compare it with the one next to it. If the middle row falls on an odd position, move to the even row behind it before comparing; otherwise you end up comparing two rows from different pairs and the count stops telling you anything.

If the two numbers are equal, the lone one is further ahead; if they are different, it is at that position or before it. Every comparison leaves you with half the logbook.

Examples

• The example

  [3, 3, 7, 7, 9, 12, 12] → 9

• The first one ended up alone

  [4, 7, 7, 11, 11] → 4

• The last one ended up alone

  [1, 1, 2, 2, 5] → 5

• A single row

  [6] → 6

• The lone one in the middle

  [1, 1, 4, 5, 5, 8, 8] → 4

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

You start with this

def lone_ad(logbook):
    pass

function loneAd(logbook) {
}