Find single number in pairs of unique numbers of a Python list in O(lg n)

Question

I have a question for Divide and Conquering in programming algorithms. Suppose you are given a random integer list in Python which consists of:

1. Unique contiguous pairs of integers
2. A single integer somewhere in the list

And the conditions are exclusive, meaning while [2,2,1,1,3,3,4,5,5,6,6] is valid, these are not:

1. [2,2,2,2,3,3,4] (violates condition 1: because there are two pairs of 2s while there can only be a maximum of 1 pair of any number)
2. [1,4,4,5,5,6,6,1] (violates condition 1: because there is a pair of 1s but they are not contiguous).
3. [1,4,4,5,5,6,6,3] (violates condition 2: there are 2 single numbers, 1 and 3)

Now the question is can you find the 'single' number index in an O(lgn) algorithm?

My original jab is this:

def single_num(array, arr_max_len):

  i = 0

  while (i < arr_max_len):
    if (arr_max_len - i == 1):
      return i
    elif (array[i] == array[i + 1]):
      i = i + 2
    else:
      return i # don't have to worry about odd index because it will never happen
  
  return None 

However, the algorithm seems to run at O(n/2) time, which seems like the best it could do.

Even if I use divide and conquer, I don't think it's going to get better than O(n/2) time, unless there's some method that's beyond my scope of comprehension at the moment.

Anyone has any better idea, or can I arguably say, this is already in O(log n) time?

EDIT: It seems like Manuel has the best solution, if allowed Ill have some time to implement a solution myself for understanding, and then accept Manuel’s answer.

Answer 1

Solution

Just binary search the even indexes to find the first whose value differs from the next value.

from bisect import bisect

def single_num(a):
    class E:
        def __getitem__(_, i):
            return a[2*i] != a[2*i+1]
    return 2 * bisect(E(), False, 0, len(a)//2)

Explanation

Visualization of the virtual "list" E() that I'm searching on:

       0  1   2  3   4  5   6  7   8  9   10 (indices)
  a = [2, 2,  1, 1,  3, 3,  4, 5,  5, 6,  6]
E() = [False, False, False, True,  True]
       0      1      2      3      4     (indices)

In the beginning, the pairs match (so != results in False-values). Starting with the single number, the pairs don't match (so != returns True). Since False < True, that's a sorted list which bisect happily searches in.

Alternative implementation

Without bisect, if you're not yet tired of writing binary searches:

def single_num(a):
    i, j = 0, len(a) // 2
    while i < j:
        m = (i + j) // 2
        if a[2*m] == a[2*m+1]:
            i = m + 1
        else:
            j = m
    return 2*i

Sigh...

I wish bisect would support giving it a callable so I could just do return 2 * bisect(lambda i: a[2*i] != a[2*i+1], False, 0, len(a)//2). Ruby does, and it's perhaps the most frequent reason I sometimes solve coding problems with Ruby instead of Python.

Testing

Btw I tested both with all possible cases for up to 1000 pairs:

from random import random

for pairs in range(1001):
    a = [x for _ in range(pairs) for x in [random()] * 2]
    single = random()
    assert len(set(a)) == pairs and single not in a
    for i in range(0, 2*pairs+1, 2):
        a.insert(i, single)
        assert single_num(a) == i
        a.pop(i)