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
```

**@daviantan1890 @ruichang** Thank you for your comments and discussions.

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.