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

Question

I am trying to count the number of unique numbers in a sorted array using binary search. I need to get the edge of the change from one number to the next to count. I was thinking of doing this without using recursion. Is there an iterative approach?

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])

Thank you.

Edit: Even if the runtime benefit is negligent from o(n), what is my binary search missing? It's confusing when not looking for an actual item. How can I fix this?

Answer 1

Working code exploiting binary search (returns 3 for given example).

As discussed in comments, complexity is about O(k*log(n)) where k is number of unique items, so this approach works well when k is small compared with n, and might become worse than linear scan in case of 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]))