Find a number where it appears exactly N/2 times

Here is my attempt at a proof of why this cannot be done in less than O(n) array accesses (for worst case, which surely is the only interesting case in this example):

Assume a worst case log(n) algorithm exists. This algorithm accesses the array at most log(n) times. Since it can make no assumptions about which elements are where, let me choose which log(n) elements it sees. I will choose to give it the first log(n) unique elements. It has not found the duplicate yet, and there still exist n/2 - log(n) unique elements for me to feed it if need be. In fact, I cannot be forced to feed it a duplicated number until it has read n/2 elements. Therefore such an algorithm cannot exist.

From a purely intuitive standpoint, this just seems impossible. Log(4 billion) is 32. So with an array of 4 billion numbers, 2 billion of which are unique, in no particular order, there is a way to find the duplicated element by only checking 32 elements?

I think you simply need to parse through the array keeping a backlog of two elements. As N/2 are equal and the rest is guaranteed to be distinct there must be one place i in your array where

a[i] == a[i-1] OR a[i] == a[i-2]

iterate once through your array and you have complexity of roughly 2*N which should be well inside O(N).

This answer is somewhat similar to the answer by Ganesh M and Dougie, but I think a little simpler.

Suppose you have a python algorithm like this:

import math
import random

def find_duplicate(arr, gap):
    cost, reps = 0, 0
    while True:
        indexes = sorted((random.randint(0,len(arr)-i-1) for i in xrange(gap)), reverse=True)
        selection = [arr.pop(i) for i in indexes]
        selection_set = set(selection)
        cost += len(selection)
        reps += 1
        if len(selection) > len(selection_set):
            return cost, reps

The idea is that arr is your set of values and gap is the log base-2 of the size. Each time you select gap elements and see if there are duplicated values. If so, return your cost (in count of elements examined) and the number of iterations (where you examine log2(size) elements per iteration). Otherwise, look at another gap-sized set.

The problem with benchmarking this algorithm is that the creation of the data each time through the loop and alteration of the data is expensive, assuming a large amount of data. (Initially, I was doing 1 000 000 elements with 10 000 000 iterations.)

So let's reduce to an equivalent problem. The data is passed in as n/2 unique elements and n/2 repeated elements. The algorithm picks the random indexes of log2(n) elements and checks for duplicates. Now we don't even have to create the data and to remove elements examined: we can just check if we have two or more indexes over the halfway point. Select gap indexes, check for 2 or more over the halfway point: return if found, otherwise repeat.

import math
import random

def find_duplicate(total, half, gap):
    cost, reps = 0, 0
    while True:
        indexes = [random.randint(0,total-i-1) for i in range(gap)]
        cost += gap
        reps += 1
        above_half = [i for i in indexes if i >= half]
        if len(above_half) >= 2:
            return cost, reps