CODEWITHSUNDEEP
algorithmsortingdata-structures
Abp
Abp

Reputation: 153

Algorithm to find the Rank of K in Sorted Array A

This is a Practice Exam question. I don't except a full answer but any hint or improvement will be appreciated.

The Search problem is that of, given(A,K), where A is sorted, find the rank of k in A, that is, find out how many elements are less than k in A. Suppose that A is already loaded in memory (so you don't count the time to read A- maybe because you are going to do lots of searches in A, and so you only have to read it once).

Give an Algorithm to solve the Search, and found the lower bound for any algorithm that solves this problem, assuming that k can only be compared with elements of A.

What I have so far. Since the array is sorted and we do not know the size n of the Array since its not given, we don't have proper bound to use binary search. So in order to find position of key, 

first we find bounds and then apply binary search algorithm.  

Let low be pointing to 1st element and high pointing to 2nd element of array, Now compare key with high index element,

->if it is greater than high index element then copy high index in low index and double the high index.

->if it is smaller, then apply binary search on high and low indices found.

And since we are using binary search the complexity will be lon(n).

Can someone tell if this is correct of given a hint on how to go on solving this. Thank you

Upvotes: 1

Views: 1608

Answers (1)

Prashanth Debbadwar
Prashanth Debbadwar

Reputation: 1047

 private int rank(int lo, int hi, int[] items, int element) {
    int mid = 0;
    int highestRank = hi;
    while (lo <= hi) {
        mid = lo + (hi - lo) / 2;
        if (element < items[mid]) {
            hi = mid - 1;
        } else if (element > items[mid]) {
            lo = mid + 1;
        } else {
            return highestRank + 1 - mid;
        }

    }
    int elementPosition = hi;
    int rank;
    if (elementPosition > highestRank) {
        rank = 1;
    } else if (elementPosition < 0) {
        rank = highestRank + 1 + 1;
    } else {
        rank = highestRank + 1 - elementPosition;
    }
    return rank;
}

This method works if items array is sorted and there shouldn't be any duplicates.

Upvotes: 2

Related Questions