275. H-Index II

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

Solution: we can use the linear solution I used in 

274. H-Index

Or we can use a better binary search.

The same idea as we do the linear search.

length-m is the target we try to figure it out.

If current paper has the same citations (citations[m]) as the amount of paper that has at least current citations ( length-m), it means H-index is citations[m] because any larger h (index to right) will lead to less paper. 

If length-m > current paper's citations, we should search right half because, length-m is too large that we can't find lenth-m of paper that have at least length-m citations. Because the most (length-m)th paper has citations of citations[m] which is less than length-m. 

else if length-m < current paper's citations, we should search left half, because although it satisfy the requirement but it is not the optimal answer.

  public int hIndex(int[] citations) {  
     int n=citations.length;  
     int l=0;  
     int r=n-1;  
     while(l<=r){  
       int m=(r-l)/2+l;  
       if(n-m==citations[m]) return n-m;  
       else if(n-m<citations[m]) r=m-1;  
       else l=m+1;  
     }  
     return n-l;  
   }