Better algo for finding the number of repetitions of an element , given a sorted array with elements repeated any no. of times

Question

I have tried for binary search for given element and traversed it leftward and rightward till it gets element greater or lesser than it, but it goes till O(n) time complexity if all elements are same. Can any better algo is there.

Answer 1

You could use a binary search that finds the lower bound of a range (and/or the upper bound) and do binary searches for the lower bound, and either the upper bound, or the lower bound of a range of elements one larger than the one you care about.

Edit: most of the code I've seen for finding the lower bound is (I believe) a bit more complex than really necessary.

int *find(int *left, int *right, int val) {
    assert(left<right);
    while (left < right) {
        int *middle = left + (right - left) / 2;
        if (*middle < val)
            left = middle + 1;
        else
            right = middle;
    }
    return left;
}

Answer 2

Do two binary searches:

In the first search you choose the left half if the middle element equals the sought element.

In the second search you choose the right half if the middle element equals the sought element.

Sample code in Java:

class Test {

    public static int findElem(int[] arr, int elem, int l, int h,boolean first) {
        if (h - l <= 1)
            return first ? (arr[l] == elem ? l : h) : (arr[h] == elem ? h : l);

        int m = l + (h - l) / 2;

        if (arr[m] < elem || (arr[m] == elem && !first))
            return findElem(arr, elem, m, h, first);

        return findElem(arr, elem, l, m, first);
    }

    public static int findElem(int[] arr, int elem, boolean first) {
        return findElem(arr, elem, 0, arr.length, first);
    }

    public static void main(String[] args) {
        int[] arr = { 0, 1, 2, 2, 2, 3, 3, 4, 4, 5 };

        int elem = 2;

        System.out.println("First index: " + findElem(arr, elem, true));
        System.out.println("Last index : " + findElem(arr, elem, false));
    }
}

Answer 3

You should binary-search for the first and the last elements of your matching sequence. If you are using C++, there are functions like lower_bound and upper_bound in the STL that let you do that. Otherwise, it's a simple modification to the algorithm.

Alternatively, you could use 3 binary searches:

1. Binary search for any element that matches your value
2. Binary search for the left side of your range
3. Binary search for the right side of the range

However, being able to do the last 2 means that you have achieved the first solution (by finding the lower/upper bounds)

Answer 4

If you are going to do this more than once, you could create a hash table with the element values as key and the index of the first and last element as value.

Reading the data to create the hash table is an O(n) operation, but then looking up the indexes is close to an O(1) operation.

Answer 5

Consider you have a sorted array a of n elements of type T. Then for certain element x you can find the number of repetition of it as follows:

T* ub = upper_bound( a, a + n, x );
int answer = ub - lower_bound( a, ub, x );

The complexity is obviously O(logn). When all elements are the same or there is no element x in a, upper_bound will return to a+n and lower_bound will work on the whole interval, which will make 2 * logn iterations on these worst cases.