Binary search in python with explanation


  • 0
    L

    My idea is using binary search.

    1. Suppose we have a list of citation [3,0,6,1,5]. First, sort the
      citation in decreasing order --> [6,5,3,1,0]

    2. Now it is obvious that we need to find the one whose number of citation is just >= its
      index+1 (citations[i] >= i+1), and those who is after this element,
      the number of citation should <= its index + 1(citations[i] < i+1).
      This is because, if we look from left to right, the index+1 shows us
      how many elements appears for now, and we want to find how many
      elements whose number of citation > the number of those elements.

    3. Therefore, using binary search. Reduce the size of list by comparing
      citations[mid] with mid+1

    ========================================================================

    def hIndex(self, citations):
        """
        :type citations: List[int]
        :rtype: int
        """
        if citations == []:
            return 0
        citations.sort(reverse = True)
        end = len(citations) - 1
        start = 0
        while start < end - 1:
            mid = (start + end) / 2
            if citations[mid] < mid + 1: # cut the right part and remain left part
                end = mid
            elif citations[mid] == mid + 1: # just the answer
                return mid+1
            else: # remain the right part
                start = mid
        # If only two elements left, check if all the citation>=index+1 or h-index=0 or just around the boundary
        if citations[end] >= end + 1:
            return end + 1
        elif citations[start] < start + 1:
                return 0
        else:
            return start + 1

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.