This is a follow up on H-Index. What if the citations array is sorted in ascending order? Could you optimize your algorithm?

Problem

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

According to the definition of h-index on Wikipedia: A scientist has an index h if h of their n papers have at least h citations each, and the other n − h papers have no more than h citations each.

If there are several possible values for h, the maximum one is taken as the h-index.

You must write an algorithm that runs in logarithmic time.

Examples

Example 1:

1
2
3
4
5
6

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:

1
2
3
4

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

Solution

Method 1 - Binary Search

This is very similar to H-Index, only thing is we don’t have to sort the citations array anymore. We can use binary search Method 3 from H-Index, where time complexity will be O(log N):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

public int hIndex(int[] citations) {
	int n = citations.length;
	int lo = 0, hi = n - 1;
	while (lo <= hi) {
		int mid = lo + (hi - lo) / 2;
		
		if (citations[mid] == n - mid) {
			return n - mid;
		} else if (citations[mid] < n - mid) {
			lo = mid + 1;
		} else { 
			//(citations[mid] > n-mid), mid qualified as a hIndex,
		    // but we have to continue to search for a higher one.
			hi = mid - 1;
		}
	}
	return n - lo;
}