# O(logN)-time O(1)-space Easy Solution with Detailed Explanations (C++/Java/Python)

• The basic idea of this solution is to use binary search to find the minimum `index` such that

``````citations[index] >= length(citations) - index
``````

After finding this `index`, the answer is `length(citations) - index`.

This logic is very similar to the C++ function `lower_bound` or `upper_bound`.

Complexities:

• Time: O(log n)
• Space: O(1)

C++:

``````class Solution {
public:
int hIndex(vector<int>& citations) {
int size = citations.size();

int first = 0;
int mid;
int count = size;
int step;

while (count > 0) {
step = count / 2;
mid = first + step;
if (citations[mid] < size - mid) {
first = mid + 1;
count -= (step + 1);
}
else {
count = step;
}
}

return size - first;
}
};
``````

Java:

``````public class Solution {
public int hIndex(int[] citations) {
int len = citations.length;

int first = 0;
int mid;
int count = len;
int step;

while (count > 0) {
step = count / 2;
mid = first + step;
if (citations[mid] < len - mid) {
first = mid + 1;
count -= (step + 1);
}
else {
count = step;
}
}

return len - first;
}
}
``````

Python:

``````class Solution(object):
def hIndex(self, citations):
"""
:type citations: List[int]
:rtype: int
"""

length = len(citations)

first = 0
count = length

while count > 0:
step = count / 2
mid = first + step
if citations[mid] < length - mid:
first = mid + 1
count -= (step + 1)
else:
count = step

return length - first
``````

I am very sure that two-branch binary search is more efficient than three branch binary search.
and (low + high) is not good idea since it may rely on the overflow behavior.
In fact, using `count` `step` `first` `mid` is the standard implement way of C++, so I do not think there are better ways to implement the binary search.

• Hi, zhiqing_xiao. Your idea is really nice. Well, I cheat the problem using `lower_bound` based on your idea :-)

``````class Solution {
public:
int hIndex(vector<int>& citations) {
int n = citations.size();
for (int i = 0; i < n; i++)
citations[i] -= (n - i);
auto lb = lower_bound(citations.begin(), citations.end(), 0);
return n - (lb - citations.begin());
}
}; ``````

• @jianchao.li.fighter Thank you for your comment. Please also notice that the for loop in your code is O(n).

• Hi, zhiqing_xiao. Yeah, you're right. Well, in fact I just take a quick test of your idea :-)

• ``````class Solution {
public:
int hIndex(vector<int>& c) {
int n = c.size();
int low = 0, high = n;
while(low<=high){
if(low == high){
return n-high;
}
int mid= (low+high)>>1;
if(c[mid] >= n - mid) high=mid;
else low = mid+1;
}
}
};
``````

ans is [0, n] which is very important, as mid can be sure to be<n, so no out of range

• I think return immediately would be better than we wait until the end. Like the following code:

Java:

``````public class Solution {
public int hIndex(int[] citations) {
int n = citations.length;
int start = 0;
int end = n-1;
int middle;
while (start <= end){
middle = (end-start)/2 + start;
if (citations[middle] == n-middle) return citations[middle];
else if(citations[middle] < n-middle) start = middle + 1;
else end = middle - 1;
}
return n - end - 1;
}
}
``````

Python

``````class Solution(object):
def hIndex(self, citations):
n = len(citations)
start, end = 0, n-1
while start <= end:
middle = (start + end) / 2
if citations[middle] == n-middle: return citations[middle]
elif citations[middle] < n - middle: start = middle + 1
else: end = middle - 1
return n-end-1
``````

C++

``````class Solution {
public:
int hIndex(vector<int>& citations) {
int n = citations.size();
int start = 0;
int end = n - 1;
int middle = 0;
while(start <= end){
middle = (end-start)/2 + start;
if (citations[middle] == n-middle) return citations[middle];
else if(citations[middle] < n-middle) start = middle + 1;
else end = middle - 1;
}
return n-end-1;
}
};  ``````

• Could you explain for me, why the result is "size - left", please ???

• In reality no human can cause overflow even if you call `low + high`.
Common professors have only about 30 h-index.

• This post is deleted!

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