Suppose I have a sorted array, and each element may appear multiple times.To make it simple, here is an example:[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3]The expected output is the number of each element. In this example, the results are:number of 1 is 17number of 2 is 6number of 3 is 9I want to find a solution where the algorithm time complexity is lower than \$O(n)\$. My idea is similar to binary search:When I meet with equal neighbour, I will jump the tail pointer by 1, by 2, by 4, etc. and at the same time, I will make cur pointer move to the tail positionWhen I meet with unequal case, I will shrink the tail pointer to be in the middle of cur and tailThe diff between cur and last element tail is the count of the current elementsAny advice on algorithm time complexity improvement, code bugs or general code style advice is appreciated.from collections import defaultdictimport randomdef generate_count(numbers):    last_index = -1    result = defaultdict(int)    cur_index = last_index + 1    tail_index = cur_index + 1    while cur_index < len(numbers):        while cur_index < tail_index and cur_index < len(numbers) and tail_index < len(numbers):            if numbers[cur_index] == numbers[tail_index]:                pre = cur_index                cur_index = tail_index                tail_index += (tail_index - pre)            else:                tail_index = (cur_index+tail_index) / 2        result[numbers[cur_index]] = cur_index - last_index        last_index = cur_index        cur_index = last_index + 1        tail_index = cur_index + 1    return resultif __name__ == __main__:    numbers = []    for i in range(random.randint(1,20)):        numbers.append(1)    print 'number of 1 is', i+1    for i in range(random.randint(1, 20)):        numbers.append(2)    print 'number of 2 is', i+1    for i in range(random.randint(1, 20)):        numbers.append(3)    print 'number of 3 is', i+1    print numbers    print generate_count(numbers)
Counting the number of elements in a sorted array
python;performance;algorithm;python 2.7;binary search