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));
    }
}