Бинарный поиск Python, находящий все не повторяющиеся числа

Этого вполне можно добиться, если список сначала отсортирован. Вот как это должно работать: (цитата из различных веб-источников) Этот пример, показанный здесь, просто пытается найти один повторяющийся номер.

Это можно сделать за время O(Log n). Наблюдение здесь:

Все числа перед требуемым имеют первое вхождение в четном индексе (0, 2, ..) и следующее вхождение в нечетном индексе (1, 3, …). И все элементы после обязательных элементов имеют первое вхождение по нечетному индексу и следующее вхождение по четному индексу.

1. Найдите средний индекс, скажем, «середина».
2. Если «середина» четная, то сравните A[mid] и A[mid + 1]. Если оба одинаковы, то требуемый элемент после «mid», еще до середины.
3. Если «середина» нечетная, то сравните A[mid] и A[mid – 1]. Если оба одинаковы, то требуемый элемент после «mid», еще до середины.

Давайте возьмем фрагмент кода для демонстрации идеи/шагов:

    def binary_search(A, l, h):
        # l: low, h: high  <- Base case
        if l > h: return None
        if l == h: return A[l]
    
        # the middle point
        mid = (h + l)//2
    
        # If mid is even ...
        if mid % 2 == 0:
            if A[mid] == A[mid+1]:
                return binary_search(A, mid+2, h)
            else:
                return binary_search(A, l, mid)
        else:
            if A[mid] == A[mid-1]:    # mid is odd
                return binary_search(A, mid+1, h)
            else:
                return binary_search(A, l, mid-1)
    
    # Test code
    A = [1, 1, 3, 4, 4, 5, 5]
    
    single = binary_search(A, 0, len(A)-1)
    
    print(f'The unique number is {single} ')

 Output:
        3