# H-Index II

Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?

Hint:

Expected runtime complexity is in O(log n) and the input is sorted.

Tips:

The basic idea of this solution is to use binary search to find the minimum index such that

``````citations[index] >= length(citations) - index
``````

Just binary search, each time check citations[mid]

1. case 1: citations[mid] == len-mid, then it means there are citations[mid] papers that have at least citations[mid] citations.
2. case 2: citations[mid] > len-mid, then it means there are citations[mid] papers that have more than citations[mid] citations, so we should continue searching in the left half
3. case 3: citations[mid] < len-mid, we should continue searching in the right side

After iteration, it is guaranteed that right+1 is the one we need to find (i.e. len-(right+1) papars have at least len-(righ+1) citations)

Code:

``````public class Solution {
public int hIndex(int[] citations) {
int len = citations.length;
if (len == 0) {
return 0;
}
int left = 0;
int mid;
int right = len - 1;
while (left <= right) {
mid = left + (right - left) / 2;
if (citations[mid] >= (len - mid)){
right = mid - 1;
} else {
left = mid + 1;
}
}
return len - (right + 1);
}
}
``````