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.

Solution:

  1. public class Solution {
  2.   public int hIndex(int[] citations) {
  3.     int n = citations.length;
  4.     int lo = 0, hi = n - 1;
  6.     while (lo <= hi) {
  7.       int mid = lo + (hi - lo) / 2;
  9.       if (citations[mid] >= n - mid) {
  10.         hi = mid - 1;
  11.       } else {
  12.         lo = mid + 1;
  13.       }
  14.     }
  16.     return n - 1 - hi;
  17.   }
  18. }