ollow 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.

**Understand the problem:**

Since the problem asks for a O(log n) solution, we can think of using a binary search.

**Code (Java):**

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

## No comments:

## Post a Comment