python - 在 O(lg n) 中查找 Python 列表的唯一数字对中的单个数字

Question

我有一个关于编程算法中的分而治之的问题。假设你在 Python 中得到一个随机整数列表，它包括:

唯一连续整数对

列表中某处的单个整数

并且条件是排他的，意思是 while [2,2,1,1,3,3,4,5,5,6,6]是有效的，这些不是:

[2,2,2,2,3,3,4] (违反条件1:因为有两对2，而任何数最多只能有一对)

[1,4,4,5,5,6,6,1] (违反条件 1:因为有一对 1 但它们不连续)。

[1,4,4,5,5,6,6,3] (违反条件2:有2个单号，1和3)

现在的问题是你能在 O(lgn) 算法中找到“单个”数字索引吗？
我原来的刺拳是这样的:

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 

然而，该算法似乎以 O(n/2) 的时间运行，这似乎是它所能做的最好的。
即使我使用分而治之，我也不认为它会比 O(n/2) 时间更好，除非有一些方法超出了我目前的理解范围。
任何人都有更好的主意，或者我可以说，这已经是 O(log n) 时间了吗？
编辑:似乎 Manuel 有最好的解决方案，如果允许的话，我将有一些时间自己实现解决方案以供理解，然后接受 Manuel 的回答。

Answer 1

解决方案
只需对偶数索引进行二分搜索即可找到第一个值与下一个值不同的值。

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)

解释
虚拟“列表”的可视化E()我正在寻找:

       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)

一开始，这些对匹配(所以 != 结果是 False -values)。从单个数字开始，对不匹配(因此 != 返回 True )。自 False < True , 这是一个排序列表 bisect愉快地搜索。
替代实现
无 bisect ，如果您还没有厌倦编写二进制搜索:

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

叹...
祝bisect会支持给它一个可调用的，这样我就可以做 return 2 * bisect(lambda i: a[2*i] != a[2*i+1], False, 0, len(a)//2) . Ruby does ，这可能是我有时使用 Ruby 而不是 Python 解决编码问题的最常见原因。
测试
顺便说一句，我对最多 1000 对的所有可能情况进行了测试:

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)