The inLeft predicate is A[M] < N - M which is true for those citations DO NOT meet the h-index requirement. It splits the array into the following two parts.
If inLeft(M) then we should set L = M + 1, otherwise R = M - 1.
In the end, L points to the first in-the-right-part value, i.e. the first citation that is good to be included in the h-index, and the corresponding h-index is N - L.
Let L = 0, R = N - 1, M = (L + R) / 2, and f(M) = A[M] - M - 1 is the count of missing numbers in the subarray A[0..M].
We'd like to find the last element whose f(M) < k which is the last element before the target missing number. Assume it's index is t, then t + 1 + k is the answer.
So we can define isLeft(M) as f(M) < k, and it will split the array into two parts:
Symmetrical and no-brainer: L = M + 1 and R = M - 1.
Con:
L and R might go out of boundary in the end.
Solution: Simply do an out-of-boundary check.
Need to think about using L or R in the end.
Solution: Take the first binary search for example, if A[M] < target, we move L. If A[M] >= target, we move R. In the end, L and R will swap order, so R will point to the last A[i] < target, and L will point to the first A[i] >= target. Thus, we should use L as the left boundary.
Solution 2. Binary Search (L < R)
Pro:
In the end, L and R points to the same position.
Con:
Need to think about setting L = M or R = M. Solution: Take the first binary search for example. If A[M] < target, we want to move L to M + 1 because A[M] != target. If A[M] >= target, we want to move R to M. Since we are using R = M, we need to make sure M != R, thus we should round down M as (L + R) / 2.
Now consider the second binary search. If A[M] > target, we want to move R to M - 1. If A[M] <= target, we want to move L to M. Since we are using L = M, we need to make sure M != R, thus we should round up M as (L + R + 1) / 2.
Overall, if we do L = M, we round up. If we do R = M, we round down.
// Initially
L R
v v
[ inLeft (A[M] < N - M) ] [ !inLeft (A[M] >= N - M) ]
// Finally
R L
v v
[ inLeft (A[M] < N - M) ] [ !inLeft (A[M] >= N - M) ]
// OJ: https://leetcode.com/problems/h-index-ii/
// Author: github.com/lzl124631x
// 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;
}
};
A = [2,3,4,7,11], k = 5
A = [ 2 3 4 7 11 ]
f = [ 1 1 1 3 6 ]
Now split `A` according to `f`
This is the one we're looking for
v
R L
v v
A = [ 2 3 4 7 ] [ 11 ]
f = [ 1 1 1 3 ] [ 6 ]
The index of 7 is 3, so the answer is 3 + 1 + k = 9
// OJ: https://leetcode.com/problems/kth-missing-positive-number/
// Author: github.com/lzl124631x
// Time: O(logN)
// Space: O(1)
class Solution {
public:
int findKthPositive(vector<int>& A, int k) {
int L = 0, R = A.size() - 1;
while (L <= R) {
int M = (L + R) / 2;
if (A[M] - M - 1 < k) L = M + 1;
else R = M - 1;
}
return L + k;
}
};
// OJ: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
// Author: github.com/lzl124631x
// Time: O(logN)
// Space: O(1)
class Solution {
public:
vector<int> searchRange(vector<int>& A, int target) {
if (A.empty()) return {-1,-1};
int N = A.size(), L = 0, R = N - 1;
while (L <= R) {
int M = (L + R) / 2;
if (A[M] < target) L = M + 1;
else R = M - 1;
}
if (L >= N || A[L] != target) return {-1,-1};
int left = L;
L = 0, R = N - 1;
while (L <= R) {
int M = (L + R) / 2;
if (A[M] > target) R = M - 1;
else L = M + 1;
}
return {left, R};
}
};
// OJ: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
// Author: github.com/lzl124631x
// Time: O(logN)
// Space: O(1)
class Solution {
public:
vector<int> searchRange(vector<int>& A, int target) {
if (A.empty()) return {-1,-1};
int N = A.size(), L = 0, R = N - 1;
while (L < R) {
int M = (L + R) / 2;
if (A[M] < target) L = M + 1;
else R = M;
}
if (A[L] != target) return {-1,-1};
int left = L;
L = 0, R = N - 1;
while (L < R) {
int M = (L + R + 1) / 2;
if (A[M] > target) R = M - 1;
else L = M;
}
return {left, L};
}
};