Question
Formatted question description: https://leetcode.ca/all/275.html
275 HIndex II
Given an array of citations sorted in ascending order (each citation is a nonnegative integer) of a researcher,
write a function to compute the researcher's hindex.
According to the definition of hindex on Wikipedia:
"A scientist has index h if
h of his/her N papers have at least h citations each,
and the other N − h papers have no more than h citations each."
Example:
Input: citations = [0,1,3,5,6]
Output: 3
Explanation: [0,1,3,5,6] means the researcher has 5 papers in total and each of them had
received 0, 1, 3, 5, 6 citations respectively.
Since the researcher has 3 papers with at least 3 citations each and the remaining
two with no more than 3 citations each, her hindex is 3.
Note:
If there are several possible values for h, the maximum one is taken as the hindex.
Follow up:
This is a follow up problem to HIndex, where citations is now guaranteed to be sorted in ascending order.
Could you solve it in logarithmic time complexity?
Algorithm
First initialize left and right to 0 and len1, then take the middle value mid, compare citations[mid] with lenmid,
 If the former is big, right moves before mid
 On the contrary, right moves after mid
The loop condition is left<=right, and finally returns
lenleft
.
Code
Java

public class H_Index_II { class Solution { public int hIndex(int[] citations) { int len = citations.length, left = 0, right = len  1; while (left <= right) { int mid = (left + right) / 2; if (citations[mid] == len  mid) { return len  mid; } else if (citations[mid] > len  mid) { // cites > h`, try next round right = mid  1; } else { left = mid + 1; } } return len  left; } } }

// OJ: https://leetcode.com/problems/hindexii/ // Time: O(logN) // Space: O(1) class Solution { public: int hIndex(vector<int>& A) { int N = A.size(), L = 0, R = N  1; while (L <= R) { int M = (L + R) / 2; if (A[M] >= N  M) R = M  1; else L = M + 1; } return N  L; } };

class Solution(object): def hIndex(self, citations): """ :type citations: List[int] :rtype: int """ if not citations: return 0 n = len(citations) start, end = 0, n  1 while start < end: mid = start + (end  start) / 2 if citations[mid] >= n  mid: end = mid else: start = mid + 1 return n  start if citations[start] != 0 else 0