设计 O(log n) 算法以在列表中查找 3 个不同的元素

Question

问题是：

设计一个 O(log n) 算法，其输入是一个排序列表 A。如果 A 包含至少 3 个不同的元素，则该算法应该返回 true。否则，算法应返回 false。

因为它必须是 O(log n)，所以我尝试使用二进制搜索，这是我写的代码：

def hasThreeDistinctElements(A):
    if len(A) < 3:
        return False
    minInd = 0
    maxInd = len(A)-1
    midInd = (maxInd+minInd)//2
    count = 1
    while minInd < maxInd: 
        if A[minInd] == A[midInd]:
            minInd = midInd
            if A[maxInd] == A[midInd]:
                maxInd = midInd
            else:
                count += 1
                maxInd -= 1
        else:
            count += 1
            minInd += 1
        midInd = (maxInd+minInd)//2
  
    return count >= 3    

有一个更好的方法吗？

谢谢

Answer 1

from bisect import bisect

def hasThreeDistinctElements(A):
    return A[:1] < A[-1:] > [A[bisect(A, A[0])]]

第一次比较安全^(*)检查是否有两个不同的值。如果是，我们检查第一个大于 的值A[0]是否也小于A[-1]。

(*)：如果A为空则不会崩溃。

或者没有bisect，二进制搜索中的第三个值A[1:-1]。不变的是，如果有的话，它必须在A[lo : hi+1]：

def hasThreeDistinctElements(A):
    lo, hi = 1, len(A) - 2
    while lo <= hi:
        mid = (lo + hi) // 2
        if A[mid] == A[0]:
            lo = mid + 1
        elif A[mid] == A[-1]:
            hi = mid - 1
        else:
            return True
    return False