Enough papers cited enough times
Find the h-index of a sorted citation list by binary searching the position where the number of papers left meets the citations. About 12 minutes.
A condition that flips once
A researcher's papers are listed with their citations, sorted from fewest to most. The h-index is the largest h such that at least h papers have h or more citations. With a sorted list, look at position i: n minus i papers are at position i or later, and all of them have at least the citations at position i.
So if the citations at position i are at least n minus i, then n minus i papers qualify. This is false for early positions and true for later ones. It flips once, so you can search for the flip.
n = len(cites) at_mid = n - mid # papers from mid on ok = cites[mid] >= at_mid
The middle is position 2, with 4 citations. Four papers (positions 2 to 5) are at or after it. 4 is at least 4, so it works. Look earlier.
The answer is what's left
The first position where the condition holds gives the biggest group, because earlier positions fail and a group starting later is smaller. The answer is the number of papers from that position to the end.
If the condition never holds, the search ends past the last position and the answer is 0 papers.
At position i, there are 4 papers from there on and the citation count is 6. Does the condition hold?
- AYes: 6 is at least 4
- BNo: 6 is more than 4
- CYou need the other papers
Show the answer
Yes: 6 is at least 4. Four papers each have at least 6 citations, so h could be 4.
H-index of a sorted list
citations is a list of whole numbers sorted from smallest to largest, the number of times each of a researcher's papers has been cited. The h-index is the largest h such that at least h papers have h or more citations each. Return the h-index.
citations = [0, 1, 3, 5, 6] → 3
0 ≤ papers ≤ 100,000 · 0 ≤ citations ≤ 1,000,000,000