Skip to content

Latest commit

 

History

History
242 lines (190 loc) · 8.65 KB

binary-search.md

File metadata and controls

242 lines (190 loc) · 8.65 KB

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

Problems that are easier if we just use binary search library function

Problems on arrays that are not sorted or monotonic

Problems that I had to use while (L < R)