如何使用二进制搜索计算排序数组中唯一数字的数量？

Question

我正在尝试使用二进制搜索计算排序数组中唯一数字的数量。我需要获得从一个数字到下一个数字的变化边缘才能计数。我正在考虑在不使用递归的情况下这样做。是否有迭代方法？

def unique(x):
    start = 0
    end = len(x)-1
    count =0
    # This is the current number we are looking for
    item = x[start]

    while start <= end:
        middle = (start + end)//2
        
        if item == x[middle]:
            start = middle+1
            
        elif item < x[middle]:
            end = middle -1
        
        #when item item greater, change to next number
        count+=1

    # if the number
    return count
    
unique([1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,5,5,5,5,5,5,5,5,5,5])

谢谢。

编辑：即使 o(n) 忽略了运行时收益，我的二分查找缺少什么？不寻找实际项目时会造成混淆。我该如何解决这个问题？

Answer 1

利用二进制搜索的工作代码（给定示例returns 3）。

正如评论中所讨论的那样，复杂度约为 O(k*log(n))，其中 k 是唯一项的数量，因此这种方法在 当 k 小于 与 n 相比时效果很好，并且在 k ~ n

的情况下可能会变得比线性扫描更糟糕

def countuniquebs(A):
    n = len(A)
    t = A[0]
    l = 1
    count = 0
    while l < n - 1:
        r = n - 1
        while l < r:
            m = (r + l) // 2
            if A[m] > t:
                r = m
            else:
                l = m + 1
        count += 1
        if l < n:
            t = A[l]
    return count

print(countuniquebs([1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,5,5,5,5,5,5,5,5,5,5]))

Answer 2

我不太会称它为“使用二进制搜索”，但是这个二进制 divide-and-conquer 算法在 O(k*log(n)/log(k)) 时间内工作，这比重复的二进制搜索，永远不会比线性扫描差：

def countUniques(A, start, end):
    len = end-start
    if len < 1:
        return 0
    if A[start] == A[end-1]:
        return 1
    if len < 3:
        return 2
    mid = start + len//2
    return countUniques(A, start, mid+1) + countUniques(A, mid, end) - 1

A = [1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,3,4,5,5,5,5,5,5,5,5,5,5]
print(countUniques(A,0,len(A)))

如何使用二进制搜索计算排序数组中唯一数字的数量？

How to count the number of unique numbers in sorted array using Binary Search?

python

algorithm

binary-search

python-3.x