CODEWITHSUNDEEP
c++complexity-theory
NotGI
NotGI

Reputation: 468

Find frequency of an element in sorted array in logn

Is this possible? I came up with this:

void binary_search(int list[], int lo, int hi, int key, int* maxIndex, int* minIndex) {
    int mid;
    if (lo > hi) {
        printf("Key not found\n");
        return;
    }
    mid = (lo + hi) / 2;
    if (list[mid] == key) {
        counter++;
        if (*maxIndex == -1) {
            *maxIndex = mid;
            cout << "Init max" << endl;
        }
        if (mid > *maxIndex) {
            *maxIndex = mid;
            cout << "Change max" << endl;
        }

        if (*minIndex == -1) {
            *minIndex = mid;
            cout << "Init min" << endl;
        }

        if (mid < *minIndex) {
            *minIndex = mid;
            cout << "Change min" << endl;
        }
    }
    if (mid - 1 >= 0)
        if (list[mid - 1] == key)
            binary_search(list, lo, mid - 1, key, maxIndex, minIndex);
    if (mid + 1 <= hi)
        if (list[mid + 1] == key)
            binary_search(list, mid + 1, hi, key, maxIndex, minIndex);
}



int main() {
    int min = 10;
    int max = -1;
    int arr[] = { 1,1,3,3,3,3,4,7,8,9 };

    binary_search(arr, 0, 10, 3, &max, &min);
    cout << max - min + 1 << endl;
    cout << counter;
    return 0;
}

What i did is, find first appearance of an element and the last appearance and deduct the indexes, But is it O(logn)?

It seems like the worst case scenario is O(n), because the recursive formula in the worst case scenario is T(n)= 2T(n/2) = O(n);

My question is, is it possible to do such thing in O(logn) ,and how will it be implemented?

Upvotes: 0

Views: 708

Answers (2)

NotGI
NotGI

Reputation: 468

I'm gonna answer my own question here. enter image description here

In pseudo code.

Upvotes: 0

eerorika
eerorika

Reputation: 238401

Find frequency of an element in sorted array in logn

Is this possible?

Yes.

What i did is, find first appearance of an element and the last appearance and deduct the indexes

That's a sensible algorithm.

But is it O(logn)?

Binary search can be implemented in O(log n) and 2 binary searches can be implemented in 2 * O(log n) = O(log n). Therefore the described algorithm can be implemented in O(log n).

Whether your implementation achieves this complexity, is another matter. But before analyzing your program, consider a flaw in it's functionality: If the key value is not in the mid point initially, the outputs will be left unmodified and give the wrong result. For example: try searching for frequency of 1 in your example.

It will be easier to analyze your algorithm if you implement the two binary searches individually... And it'll probably also be faster because a simple binary search can be tail call optimized.

ps. there is no need to re-implement binary search. The standard library already provides an implementation: std::lower_bound and std::upper_bound (and std::equal_range which does what you're asking for fully).

Upvotes: 2

Related Questions