Is there any faster( beside going through the whole loop O(n)) way to find the no of duplicates of a number from a sorted list.

Question

searching

Answer 1

I don't know if it will be faster but you don't have to go trough the whole list (it is an example in python):

l = [1, 2, 3, 3, 3, 4, 4, 5]
total = 0
z = 4
try:
for i in range (l.index(z), len(l) ):
if l[i] == z:
total += 1
if l[i] > z:
break
except:
pass
print (total)

Answer 2

If the list is sorted, you can easily find both the first and the last positions of a given number (O(logn)). Everything in between also is duplicate, no additional check is needed.

Answer 3

you mean to say i would apply binary search twice to get the first and last position and just subtract it to get the count.
Thanks didn't clicked to me.

Answer 4

In python you could use the Counter module. I can't guarantee that it is faster than O(n) but usually using the most specific module is said to give better and more efficient results than anything you create yourself.

from collections import Counter

a = [1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 4]
n = 2

print(Counter(a)[n])
#output: 17

Answer 5

The Counter module seems to be O(n), as it handles all array values during initialization.