Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/275.html
Given an array of integers citations
where citations[i]
is the number of citations a researcher received for their i^{th}
paper and citations
is sorted in ascending order, return the researcher's hindex.
According to the definition of hindex on Wikipedia: The hindex is defined as the maximum value of h
such that the given researcher has published at least h
papers that have each been cited at least h
times.
You must write an algorithm that runs in logarithmic time.
Example 1:
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, their hindex is 3.
Example 2:
Input: citations = [1,2,100] Output: 2
Constraints:
n == citations.length
1 <= n <= 10^{5}
0 <= citations[i] <= 1000
citations
is sorted in ascending order.
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

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; } } } ############ class Solution { public int hIndex(int[] citations) { int n = citations.length; int left = 0, right = n; while (left < right) { int mid = (left + right + 1) >> 1; if (citations[n  mid] >= mid) { left = mid; } else { right = mid  1; } } return 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: def hIndex(self, citations: List[int]) > int: n = len(citations) left, right = 0, n while left < right: mid = (left + right + 1) >> 1 if citations[n  mid] >= mid: left = mid else: right = mid  1 return left ############ 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

func hIndex(citations []int) int { n := len(citations) left, right := 0, n for left < right { mid := (left + right + 1) >> 1 if citations[nmid] >= mid { left = mid } else { right = mid  1 } } return left }

function hIndex(citations: number[]): number { const n = citations.length; let left = 0, right = n; while (left < right) { const mid = (left + right + 1) >> 1; if (citations[n  mid] >= mid) { left = mid; } else { right = mid  1; } } return left; }