Python二进制搜索查找所有不重复的数字

Question

我一直在尝试编写一个二进制搜索函数来查找列表中的所有唯一数字。我知道我必须找到列表的中间值，并根据数字的大小将其与第一个和最后一个元素进行比较。但我看不出所有元素是如何相互检查以找到不重复的。我可以很容易地做len(set(list((来删除所有重复项，但不知道如何在二进制搜索中使用它。

非常感谢你的帮助。

Answer 1

如果列表先按排序顺序排列，则很有可能实现这一点。这就是它应该如何工作：(引用各种网络来源(这里显示的这个例子只是试图找到一个重复的数字。

它可以在O(Log n(时间内完成。观察结果如下：

所需之前的所有数字第一次出现在偶数索引(0，2，..(，下一次出现在奇数索引(1，3，..(。所需元素之后的所有元素在奇数索引处第一次出现，在偶数索引处下一次出现。

1. 找到中间的索引，说"mid">
2. 如果"mid"是偶数，则比较A[mid]和A[mid+1]。如果两者相同，则在"mid"之后的必需元素在mid之前
3. 如果"mid"是奇数，则比较A[mid]和A[mid-1]。如果两者相同，则在"mid"之后的必需元素在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