💻
Algorithm
  • README
  • Array
    • At Most To Equal
    • Count Inversions In An Array
    • Interleaving Placement
    • Kadane
    • Left To Right State Transition
    • Permutation
    • Quick Select
    • Sliding Window
    • Two Pointers
  • Binary Tree
    • Avl Tree
    • Binary Search Tree
    • Serialization And Deserialization
    • Traversal
  • Company
    • Facebook
  • Cpp
    • Array
    • Memset 3 F
    • Overflow
  • Data Structure
    • Binary Indexed Tree
    • Segment Tree And Binary Index Tree
    • Segment Tree
    • Stack
    • Trie
    • Union Find
  • Dynamic Programming
    • Knapsack
      • 0 1 Knapsack
      • Bounded Knapsack
      • Unbounded Knapsack
    • Bitmask Dp
    • Dp On Subsets
    • Dp On Tree
    • Dp With Sorting
    • Selective State Dp
    • Travelling Salesperson
  • Graph
    • Minimum Spanning Tree
      • Kruskal
      • Prim
    • Shortest Path
      • Bellman Ford
      • Dijkstra
      • Floyd Warshall
      • Johnson
      • Shortest Path Faster Algorithm
    • Bi Directional Breadth First Search
    • Bipartite
    • Breadth First Search
    • Component Coloring
    • Component Count
    • Depth First Search
    • Eulerian Path
    • Maximum Bipartite Matching
    • Tarjan
    • Topological Sort
    • Tree Diameter
    • Tree Ring Order Traversal
  • Greedy
    • Greedy Scheduling
    • Regret Greedy
  • Math
    • Catalan Number
    • Combinatorics
    • Factorial
    • Factorization
    • Fast Pow
    • Gcd
    • Geometry
    • Get Digits
    • Lcm
    • Median Minimizes Sum Of Absolute Deviations
    • Mode
    • Modular Multiplicative Inverse
    • Palindrome
    • Prime Number
    • Round Up
    • Sieve Of Eratosthenes
    • Stars And Bars
    • Sum Of Sequence
  • Miscellaneous
    • Bin Packing
    • Floyds Tortoise And Hare
    • Hungarian
    • Palindrome
  • Sort
    • Bubble Sort
    • Cycle Sort
    • Heap Sort
    • Merge Sort
    • Quick Sort
    • Sorting
  • Stl
    • Cpp Stl
    • Istringstream
    • Lower Bound Upper Bound
    • Priority Queue
  • String
    • Kmp
    • Manacher
    • Rabin Karp
    • String Processing
    • Z
  • Backtracking
  • Binary Answer
  • Binary Lifting
  • Binary Search
  • Bit Manipulation
  • Date
  • Difference Array
  • Discretization
  • Divide And Conquer
  • Gray Code
  • Great Problems For Practice
  • Interval Scheduling Maximization
  • Io Optimization
  • K Subset Partitioning
  • Line Sweep
  • Longest Common Subsequence
  • Longest Increasing Subsequence
  • Meet In The Middle
  • Minmax
  • Mono Deque
  • Monotonic Stack
  • Offline Query
  • P And Np
  • Prefix State Map
  • Prefix Sum
  • Random
  • Reservoir Sampling
  • Reverse Polish Notation
  • Sqrt Decomposition
Powered by GitBook
On this page
  • Things to consider
  • Search Range and Loop Condition
  • When and how to change the bounds
  • What's the result
  • Examples
  • 275. H-Index II (Medium)
  • 1539. Kth Missing Positive Number (Easy)
  • Comparisons between L <= R and L < R
  • Solution 1. Binary Search (L <= R)
  • Solution 2. Binary Search (L < R)
  • Other notes
  • Problems

Was this helpful?

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

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

Comparisons between L <= R and L < R

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

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)

PreviousBinary LiftingNextBit Manipulation

Last updated 1 year ago

Was this helpful?

From , we can see that the L, R values might be different for these two templates.

275. H-Index II (Medium)
1539. Kth Missing Positive Number (Easy)
34. Find First and Last Position of Element in Sorted Array (Medium)
1337. The K Weakest Rows in a Matrix (Easy)
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)
300. Longest Increasing Subsequence (Medium)
497. Random Point in Non-overlapping Rectangles (Medium)
162. Find Peak Element (Medium)
33. Search in Rotated Sorted Array (Medium)
81. Search in Rotated Sorted Array II (Medium)
153. Find Minimum in Rotated Sorted Array (Medium)
154. Find Minimum in Rotated Sorted Array II (Hard)
658. Find K Closest Elements (Medium)