# Binary search in python with explanation

• 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

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