LeetCode //C - 275. H-Index II

275. H-Index II

Given an array of integers citations where citations[i] is the number of citations a researcher received for their $i^{th}$ paper and citations is sorted in ascending order, return the researcher’s h-index.

According to the definition of h-index on Wikipedia: The h-index is defined as the maximum value of h such that the given researcher has published at least h papers that have each been cited at least h times.

You must write an algorithm that runs in logarithmic time.
 

Example 1:

Input: citations = [0,1,3,5,6]
Output: 3
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had received 0, 1, 3, 5, 6 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, their h-index is 3.

Example 2:

Input: citations = [1,2,100]
Output: 2

Constraints:

• n == citations.length
• $1<=n<=10^5$
• 0 <= citations[i] <= 1000
• citations is sorted in ascending order.

From: LeetCode
Link: 275. H-Index II

Solution:

Ideas:

1. Initialization: Set the binary search bounds. left is initialized to 0, and right to citationsSize (the total number of papers).

2. Binary Search Loop:

• Midpoint Calculation: Compute mid as the average of left and right, adjusting for integer division.
• Condition Check: Look at the (citationsSize - mid - 1)th position in the array. This position corresponds to the (mid + 1)th last paper.
  • The index is derived from considering the mid value as the hypothesized h-index. You need mid + 1 papers with at least mid + 1 citations each.
  • By checking the paper at citationsSize - mid - 1, you are effectively checking if there are enough papers with sufficient citations to validate the hypothesized h-index.
• Adjusting Bounds:
  • If the paper at this position has at least mid + 1 citations (citations[citationsSize - mid - 1] >= mid + 1), it suggests that it’s possible there are mid + 1 papers with at least mid + 1 citations, so the h-index could be larger. Thus, move the left boundary up to explore higher h-values.
  • If not, it means mid + 1 is too high for an h-index, so adjust right to narrow the search downwards.

3. Termination: When left meets right, the binary search has honed in on the largest possible value of h that satisfies the h-index condition. Here, left or right can be returned as they converge to the same value.

Code:

int hIndex(int* citations, int citationsSize) {
    int left = 0;
    int right = citationsSize; // This will represent the maximum possible h-index which cannot exceed the number of papers
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (citations[citationsSize - mid - 1] >= mid + 1) {
            left = mid + 1; // Try for a larger h
        } else {
            right = mid; // Reduce the search space
        }
    }
    return left; // 'left' will be the maximum h-index found
}