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.
Solution:
public class Solution {
public int hIndex(int[] citations) {
int len = citations.length;
int lo=0, hi=len-1;
while(lo<=hi){
int mid = (lo+hi)/2;
if(citations[mid]<len-mid) lo=mid+1;
else if(citations[mid]>len-mid) hi=mid-1;
else return len-mid;
}
return len-lo;
}
}