H-Index II

Question

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

Tags

• Binary Search

Thought

The challenge in this problem is that the test case is much larger than the previous problem. Thus, the algorithm used in previous problem is not proper here any more.

However, considering that the citation list has been sorted, binary search should work theoretically. We can use citation[mid] to compare with the length - mid.

Code

class Solution(object):
    def hIndex(self, citations):
        """
        reference: https://discuss.leetcode.com/topic/38299/short-python-o-log-n-solution
        :type citations: List[int]
        :rtype: int
        """
        length = len(citations)
        begin, end = 0, length - 1
        while begin <= end:
            mid = (begin + end) / 2
            if citations[mid] >= length - mid:
                end = mid - 1
            else:
                begin = mid + 1
        return length - begin