778 793 1201 (binary answer)174
If it's an array, usually the search range is just [0, N-1]
and the loop condition is L <= R
.
There should be a predicate separating the array in two parts. Use it as the condition.
For example, assume there is a inLeft
function checking whether the current M = (L + R) / 2
is in the left part.
// Initially
L R
v v
[ inLeft ] [ !inLeft ]
// Finally
R L
v v
[ inLeft ] [ !inLeft ]
if (inLeft(M)) L = M + 1;
else R = M - 1;
As shown above, after the binary search, the L
points to the first not-in-left-part element while R
points to the last in-left-part element.
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.
// 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) ]
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
.
// 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;
}
};
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:
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
So the answer is R + 1 + k
or L + k
.
// 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;
}
};
34. Find First and Last Position of Element in Sorted Array (Medium)
Pro:
M
is always(L + R) / 2
- Symmetrical and no-brainer:
L = M + 1
andR = M - 1
.
Con:
L
andR
might go out of boundary in the end.
Solution: Simply do an out-of-boundary check.- Need to think about using
L
orR
in the end.
Solution: Take the first binary search for example, ifA[M] < target
, we moveL
. IfA[M] >= target
, we moveR
. In the end,L
andR
will swap order, soR
will point to the lastA[i] < target
, andL
will point to the firstA[i] >= target
. Thus, we should useL
as the left boundary.
// 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};
}
};
Pro:
- In the end,
L
andR
points to the same position.
Con:
- Need to think about setting
L = M
orR = M
. Solution: Take the first binary search for example. IfA[M] < target
, we want to moveL
toM + 1
becauseA[M] != target
. IfA[M] >= target
, we want to moveR
toM
. Since we are usingR = M
, we need to make sureM != R
, thus we should round downM
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.
Round up: (L + R) / 2
or L + (R - L) / 2
.
Round down: (L + R + 1) / 2
or R - (R - L) / 2
.
// 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};
}
};
From 1337. The K Weakest Rows in a Matrix (Easy), we can see that the L
, R
values might be different for these two templates.
Problems that are good for practicing handwriting binary search
- 704. Binary Search (Easy)
- 34. Find First and Last Position of Element in Sorted Array (Medium)
- 35. Search Insert Position (Easy)
- 275. H-Index II (Medium)
- 1539. Kth Missing Positive Number (Easy)
- 1044. Longest Duplicate Substring (Hard)
- 668. Kth Smallest Number in Multiplication Table (Hard)
Problems that are easier if we just use binary search library function
- 300. Longest Increasing Subsequence (Medium)
- 497. Random Point in Non-overlapping Rectangles (Medium)
Problems on arrays that are not sorted or monotonic
- 162. Find Peak Element (Medium)
- 33. Search in Rotated Sorted Array (Medium)
- 81. Search in Rotated Sorted Array II (Medium)
Problems that I had to use while (L < R)