h-index calculation for advice

Question

Working on an algorithm puzzle. Post problem statement and code. My question is, for the last line, whether return citations[right] is always has the same result as return len - (right+1)? I tried few test cases, and it seems both are of the same value. Want to seek advice is any anti-samples when they are different? Thanks.

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."

For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.

What if the citations array is sorted in ascending order? Could you optimize your algorithm?

class Solution {
public:
    int hIndex(vector<int>& citations) {
        int left=0, len = citations.size(), right= len-1,  mid;
        while(left<=right)
        {
            mid=(left+right)>>1;
            if(citations[mid]== (len-mid)) return citations[mid];
            else if(citations[mid] > (len-mid)) right = mid - 1;
            else left = mid + 1;
        }
        return len - (right+1);
    }
};

thanks in advance, Lin

Answer 1

First of all, your implementation works on sorted input only anyway, right?

Now imagine the input:

vector<int> v{1,2,5,6,9};

This input will return different values for:

return len - (right+1);    // returns 3 (correct answer)
return citations[right];   // returns 2 (wrong answer)

You can however do:

return len-left; 

This works beacuse right+1 will always equal left on this line (given your code).

Think about the exit condition of the while loop as well as the fact, that the difference between left and right can only change by 1 at max, on each iteartion.

---

In overall the best solution is to sort the input first and then do your binary search, giving you O(N log N) time complexity, all together.

It won`t get any better than that.

Sidenote: I would avoid code like >>1 instead of simply dividing by 2 since this impairs readability, without any benefits. I assume you are using a reasonable compiler (with optimization capablities).