Binary Search

778 793 1201 (binary answer)174

Things to consider

Search Range and Loop Condition

If it's an array, usually the search range is just [0, N-1] and the loop condition is L <= R.

When and how to change the bounds

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;

What's the result

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.

Examples

275. H-Index II (Medium)

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;
    }
};

1539. Kth Missing Positive Number (Easy)

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;
    }
};

Comparisons between L <= R and L < R

34. Find First and Last Position of Element in Sorted Array (Medium)

Solution 1. Binary Search (L <= R)

Pro:

• M is always (L + R) / 2

• 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.

// 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};
    }
};

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.

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};
    }
};

Other notes

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

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)

• 153. Find Minimum in Rotated Sorted Array (Medium)

• 154. Find Minimum in Rotated Sorted Array II (Hard)

• 658. Find K Closest Elements (Medium)