How to count how many times a value is repeated in an array using binary search?-CodePudding

I'm not able, through binary search, to count the number of times a number is repeated in a vector. Here's the code:

v = {1, 1, 2, 2, 2, 3, 4, 5}
elem = 2

n = len(v)
lef = 0
rig = n - 1

while lef <= rig:
   mid = (lef   rig) // 2
   if v[mid] == elem:
       aux= 1
       break
   elif elem < v[mid]:
       rig = mid - 1
       aux= 1
   else:
       lef = mid   1
       aux= 1

if v[mid] == elem:
  print(mid)
else:
  print(-1)

print(aux)

As you can see, I put a variable named aux serving as a counter inside the if and elif, but the output is not as expected. In the code I put the printing of the position to make sure that the algorithm in the part of finding the index is working.

I also thought about using another loop inside the while, but it soon came to mind that it would make the algorithm more expensive, but would that be the only way? How could I implement this?

CodePudding user response：

Here is a simple idea: call binary search twice. That way you won't sacrifice the time complexity.

v = [1, 1, 2, 2, 2, 3, 4, 5]
elem = 2
n = len(v)

def find_lo():
    lef = 0
    rig = n - 1
    while lef <= rig:
        mid = (lef   rig) // 2
        if v[mid] == elem:
            if not mid:
                return mid
            if v[mid] != v[mid-1]:
                return mid
            rig = mid-1
        elif elem < v[mid]:
            rig = mid - 1
        else:
            lef = mid   1
    
    return None
    
def find_right():
    lef = 0
    rig = n - 1
    while lef <= rig:
        mid = (lef   rig) // 2
        if v[mid] == elem:
            if mid >= n-1:
                return mid
            if v[mid] != v[mid 1]:
                return mid
            lef = mid 1
        elif elem < v[mid]:
            rig = mid - 1
        else:
            lef = mid   1
    
    return None

print(find_lo())    # 2
print(find_right()) # 4

Note: the two methods can be refactored as a single function to reduce redundancy, this is just a simple demonstration.

CodePudding user response：

If you can use algorithm available in python's bisect, it is just:

import bisect
v = [1, 1, 2, 2, 2, 3, 4, 5]
elem = 2
print(bisect.bisect_right(v, elem) - bisect.bisect_left(v, elem))

output:

CodePudding user response：

v = {1, 1, 2, 2, 2, 3, 4, 5} is a set, and a set cannot have duplicates

The duplicates are deleted because of the way you declared v, so you will no be able to count repetitions.

v = {1, 1, 2, 2, 2, 3, 4, 5}
print(v)

>>>{1,2,3,4,5}

You can use a list, and count the duplicates with Counter

from collections import Counter

v = [1, 1, 2, 2, 2, 3, 4, 5]

print(v)

_=[print(f"{element}: {copies} times") for element,copies in Counter(v).items()]

it outputs

[1, 1, 2, 2, 2, 3, 4, 5]
1: 2 times
2: 3 times
3: 1 times
4: 1 times
5: 1 times