Binary Search

Conditions for Binary Search

Initially, I simply thought that data needed to be monotonic to apply binary search. However, after solving some problems, I learned that the essence of applying binary search is that the data has **two segments**, meaning: one segment satisfies a certain property, while the other segment doesn't, then we can use "binary search".

Key Understanding!!!

Loop Invariant

while low <= high
1. Termination condition is always low + 1 == high, meaning low > right
2. This means every element in the interval [low..high] has been traversed
while low < high
1. Termination condition is always low == high
2. This means the element at low == high in the interval [low..high] might not have been traversed, requiring a patch
3. Note: For problems like lc.153, when using an approximation strategy to find the answer, if the two pointers end up at the same position and we don't need to perform any operations on this element (just finding it is enough), then using < is also appropriate.

Feasible Solution Interval

For each iteration of the binary search process, its feasible solution interval should be consistent. Combining this with the understanding of loop invariants:

[low...high], closed interval on both sides, generally we can determine the next search interval based on mid: low = mid + 1 or high = mid - 1
[low...high), left-closed right-open interval, maintaining the feasible solution interval, the next search interval's left side is low = mid + 1, right side is high = mid

Due to array characteristics, these are the two most commonly used intervals. Of course, there's also the open interval on both sides (low...high), corresponding to the loop invariant while low + 1 < high, but it's less common.

Also, please make sure to understand what the feasible solution interval really is! It's not just about defining pointers as low = 0, high = len - 1 and assuming the feasible solution interval is [low...high]. We need to look at the actual problem. For example, if you can determine that the solutions at low = 0 and high = len - 1 are definitely not in the results we need, then the corresponding feasible solution interval is (low...high), and accordingly, we can use the loop invariant while low + 1 < high

For problems finding left and right boundaries, we also decide the update of low or high in each round based on the feasible solution interval. For left boundary search: when mid == x, r = mid; for right boundary search: when mid == x, l = mid + 1. Note that when right boundary search ends, l = mid + 1, so the actual position of the searched data is l - 1.

Practice

lc.33 Search in Rotated Sorted Array

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
    let l = 0,
        r = nums.length - 1
    while (l <= r) {
        const mid = l + ((r - l) >> 1)
        if (nums[mid] === target) {
            return mid
        } else if (nums[mid] < nums[l]) {
            // Right half is sorted
            if (nums[mid] < target && target <= nums[r]) {
                l = mid + 1
            } else {
                r = mid - 1
            }
        } else {
            // Left half is sorted, target is in sorted interval
            if (nums[l] <= target && target < nums[mid]) {
                r = mid - 1
            } else {
                l = mid + 1
            }
        }
    }
    return -1
}

/**
 * Let's see how to rewrite the code using left-closed right-open interval
 */
var search = function (nums, target) {
    let l = 0,
        r = nums.length
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        if (nums[mid] === target) {
            return mid
        } else if (nums[mid] > nums[l]) {
            // Left half is sorted, target is in sorted interval
            if (nums[l] <= target && target < nums[mid]) {
                r = mid
            } else {
                l = mid + 1
            }
        } else {
            // Right half is sorted
            /**
             * Pay special attention here!!! Because right boundary is open interval, we compare with nums[r - 1]
             */
            if (nums[mid] < target && target <= nums[r - 1]) {
                l = mid + 1
            } else {
                r = mid
            }
        }
    }
    return -1
}

lc.34 Find First and Last Position of Element in Sorted Array

Even simpler than the previous problem~

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function (nums, target) {
    // Just finding left and right boundaries
    const res = []
    let l = 0,
        r = nums.length
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        if (nums[mid] < target) {
            l = mid + 1
        } else {
            r = mid
        }
    }
    if (nums[l] !== target) return [-1, -1] // Note: remember to check if target exists
    res[0] = l
    l = 0
    r = nums.length
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        if (nums[mid] > target) {
            r = mid
        } else {
            l = mid + 1
        }
    }
    res[1] = r - 1 // Because I'm using left-closed right-open interval, we need to subtract 1 from right boundary
    return res
}
/**
 * For boundary-finding binary search, if using closed interval on both sides, we need to check if l, r are within bounds after while
 * Because l <= r ends when l + 1 = r, which might cause out-of-bounds,
 * This problem happens to require this check
 */

When deciding based on comparing nums[mid] and target, my habit is to look at whether target is to the left or right of mid, which makes it more intuitive. For example: nums[mid] > target, intuitively means mid is to the right of target, which might be confusing at first - should we shrink left or right? (Maybe I'm just not good enough 😂) If we convert it to target being to the left of mid, we can easily imagine we need to search left, so we should shrink the right boundary.

lc.35 Search Insert Position easy

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var searchInsert = function (nums, target) {
    let l = 0,
        r = nums.length
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        if (nums[mid] === target) {
            return mid
        } else if (nums[mid] > target) {
            r = mid
        } else {
            l = mid + 1
        }
    }
    return l
}

A relatively simple problem. After looking at the official solution and comments, someone asked why we don't return immediately when we find target (the official solution doesn't return). After carefully reading the problem, since it states there won't be duplicate elements in nums, we could return immediately. The official solution considers the case with duplicate elements, turning it into a left boundary search problem.

lc.74 Search a 2D Matrix

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
    let l = 0,
        r = matrix.length
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        if (matrix[mid][0] === target) {
            return true
        } else if (matrix[mid][0] > target) {
            r = mid
        } else {
            l = mid + 1
        }
    }
    // Because we're looking for the first element >= target, i.e., finding the right boundary of first column
    if (r - 1 < 0) return false

    const row = matrix[l - 1]
    let i = 0,
        j = row.length
    while (i < j) {
        const mid = i + ((j - i) >> 1)
        if (row[mid] === target) {
            return true
        } else if (row[mid] > target) {
            j = mid
        } else {
            i = mid + 1
        }
    }
    return false
}

lc.81 Search in Rotated Sorted Array II

Compared to lc.33, this just adds duplicate elements. The problem is, if the rotation point happens to be a duplicate element, it will make the data lose its "two-segment" property:

The official solution's approach is to restore the two-segment property: if(nums[l] == nums[mid] && nums[mid] == nums[r]) {l++, r--}

For a lazy approach, we can just shrink one side, either left or right. For example, I chose to shrink the left boundary when nums[l] === nums[mid]

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {boolean}
 */
var search = function (nums, target) {
    let l = 0,
        r = nums.length
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        if (nums[mid] === target) {
            return true
        } else if (nums[mid] > nums[l]) {
            if (nums[l] <= target && target < nums[mid]) {
                r = mid
            } else {
                l = mid + 1
            }
        } else if (nums[mid] < nums[l]) {
            if (nums[mid] < target && target <= nums[r - 1]) {
                l = mid + 1
            } else {
                r = mid
            }
        } else {
            // nums[mid] === nums[l] case, shrink left boundary to restore two-segment property
            l++
        }
    }
    return false
}

/** Let's see the case of shrinking right boundary */
var search = function (nums, target) {
    let l = 0,
        r = nums.length
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        if (nums[mid] === target) {
            return true
        } else if (nums[mid] < nums[r - 1]) {
            if (nums[mid] < target && target <= nums[r - 1]) {
                l = mid + 1
            } else {
                r = mid
            }
        } else if (nums[mid] > nums[r - 1]) {
            if (nums[l] <= target && target < nums[mid]) {
                r = mid
            } else {
                l = mid + 1
            }
        } else if (nums[mid] === nums[r - 1]) {
            r--
        }
    }
    return false
}

/** For shrinking both sides, see the official solution~ */

When shrinking left boundary, compare mid with left; when shrinking right boundary, compare mid with right

lc.153 Find Minimum in Rotated Sorted Array

To be honest, this problem troubled me for a long time 😭, because it's a bit different~

Here's how I analyzed it (mid represents nums[mid], l represents nums[l]):

If the array is monotonically ordered after n rotations, the minimum is at the leftmost
If the array is unordered after n rotations, then the minimum is in the unordered half after binary search
- 2.1 mid > l, right half is unordered, choose right half (pitfall)
- 2.2 mid < l, left half is unordered, choose left half

Some test cases just wouldn't pass~ After looking at the solution, it compares with the right side 😭 why??? What's different about comparing with the left? After careful consideration, the problem was in 2.1 mid > l right side unordered, the first case is the best counterexample, where the minimum is at the leftmost so we should choose the left half. Therefore, comparing mid with l doesn't satisfy the two-segment property, while comparing with r is different:

mid > r, then right side is unordered, choose right side, ignore left
mid < r, then if left side is unordered, choose left side, ignore right; if left side is ordered, r keeps shrinking to approximate, can also get result, so can also choose left side
- Can also think of it this way: mid < r, right side is ordered, then result must be in [l..mid]

Therefore, comparing mid with r satisfies the two-segment property. (PS: comparing mid with l is also possible, just exclude the case where the entire data is monotonic before binary search, won't expand on this here)

Let's think about it again, what if we're looking for the maximum? 😁, then we should keep shrinking l to approximate, so it's suitable to compare mid with l.

Next comes the second pitfall 😭

Initially, I initialized the right boundary as r === nums.length, thinking I'd just use left-closed right-open interval like before, but some test cases didn't pass --- [4,5,1,2,3]. Why? Let's look at it, it turns out when mid happens to be the minimum value, r is updated to mid, but the traversal doesn't stop, l is still less than r, then it goes to the wrong answer.

But why didn't this happen before? I thought about it again, oh, before we always had a target, there would be a case nums[mid] === target where we return immediately; but here there's no target, we can only let the two pointers keep approximating to get the final result. According to the previous analysis, r's update strategy is r = mid, the trouble is here, let's look at its two meanings:

First meaning of r == mid, left side is unordered, discard right side, but mid could be a feasible solution, so r can't be mid -1
Second meaning of r == mid, left side is ordered, keep approximating, at this point r == mid, each approximated value could be a feasible solution, which doesn't match the feasible solution interval of [l..r)

Therefore, setting the feasible solution interval as [l..r] is appropriate, so initialize as r = nums.length - 1. (I vaguely feel there must be some mathematical logic behind this, would appreciate if any expert could enlighten me)

/** Wrong solution */
var findMin = function (nums) {
    let l = 0,
        r = nums.length // bug
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        if (nums[mid] > nums[r - 1]) {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return nums[r]
}
/**
 * Example with [2,1]
 * 1. l == 0, r == 2, mid = 1, nums[1] > nums[1] : false --> r = 1
 * 2. l == 0, r == 1, mid = 0, nums[0] > nums[0] : false --> r = 0
 * End loop l == r == 0
 *
 * We'll find that once the data coincidentally matches, it keeps comparing nums[mid] with itself
 */

/** Modified version */
var findMin = function (nums) {
    let l = 0,
        r = nums.length - 1
    // This shows that whether to use < or <= depends entirely on the problem, it's just used to control when to end traversal
    // Here, when l == r, that's the solution, so < is enough (because we don't need to do anything with the last element)
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        // Right side is unordered
        if (nums[mid] > nums[r]) {
            l = mid + 1
        } else {
            // Otherwise right side is ordered, result must be in [l..mid], so r = mid
            r = mid
        }
    }
    return nums[r]
}
/**
 * Example with [2,1]
 * 1. l == 0, r == 1, mid = 0, nums[0] > nums[1] : true --> l = mid + 1 === 1
 * End loop l == r == 1
 */

What we can learn from this problem:

Must analyze the two-segment property of the problem well, correctly choose left and right partitions, while paying attention to whether the feasible solution interval remains consistent in each round
When there's no target and we're using two pointers to detect extreme values, using [l..r] closed interval is more reliable
Looking back at l.81, for finding minimum in rotated array, we choose the unordered interval, then find the ordered interval within the unordered interval, in the ordered interval (monotonically increasing), we definitely shrink from right to left, so comparing with right side makes sense; if we were searching for maximum, then we would compare with left side.

lc.154 Find Minimum in Rotated Sorted Array II hard

Compared to lc.153, this just adds duplicate elements, a paper tiger.

var findMin = function (nums) {
    let l = 0,
        r = nums.length - 1
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        if (nums[mid] > nums[r]) {
            l = mid + 1
        } else if (nums[mid] < nums[r]) {
            r = mid
        } else {
            // nums[mid] === nums[r]
            r--
        }
    }
    return nums[r]
}

Note: In lc.153, there's also a nums[mid] === nums[r] check, but because lc.153 guarantees no duplicate data, we can directly set r = mid. When encountering duplicate data, we can't do this anymore, just like in lc.81, when duplicate data happens to be at the rotation point, it loses the two-segment property, the solution is similar.

lc.162 Find Peak Element

The solution is almost identical to lc.153, just changing from comparing mid with r to comparing mid with mid+1.

/**
 * @param {number[]} nums
 * @return {number}
 */
var findPeakElement = function (nums) {
    let l = 0,
        r = nums.length - 1
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        /**
         * mid > mid + 1, so mid could be maximum r = mid
         * otherwise mid <= mid + 1, when mid < mid + 1, l = mid + 1, when mid = mid + 1, l can also equal mid + 1
         */
        if (nums[mid] > nums[mid + 1]) {
            r = mid
        } else {
            l = mid + 1
        }
    }
    return l
}

var findPeakElement = function (nums) {
    let l = 0,
        r = nums.length - 1
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        /**
         * When mid < mid + 1, l = mid + 1
         * otherwise when mid >= mid + 1, when mid > mid + 1, r = mid; when mid = mid + 1, r can also equal mid
         */
        if (nums[mid] < nums[mid + 1]) {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return l
}

Unlike rotated array, this problem can get maximum value from left to right or right to left, so comparing mid with either side is ok.

lc.240 Search a 2D Matrix II

Unlike lc.74, the end of the previous row is no longer greater than the start of the next row. The most intuitive approach is to do binary search on each row.

/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
    for (let i = 0; i < matrix.length; i++) {
        const row = matrix[i]
        let l = 0,
            r = row.length
        while (l < r) {
            const mid = l + ((r - l) >> 1)
            if (row[mid] === target) {
                return true
            } else if (row[mid] < target) {
                l = mid + 1
            } else {
                r = mid
            }
        }
    }
    return false
}

This approach has time complexity O(mlogn). The official solution gives a better approach Z-shaped search, which starts searching from the top-right corner and updates coordinates ++y or --x based on conditions.

lc.410 Split Array Largest Sum hard

The conventional approach for this problem is dynamic programming, I really didn't expect to use binary search...

This problem is indeed difficult, just look at the official solution, it uses binary search + greedy

lc.658 Find K Closest Elements

var findClosestElements = function (arr, k, x) {
    // First find position i of x, then expand [p..q] from i to both sides until q - p + 1 === k
    let l = 0,
        r = arr.length
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        if (arr[mid] < x) {
            l = mid + 1
        } else {
            r = mid
        }
    }
    /**
     * Key point, at this point l == r, and [r..] are all **greater than or equal to** x; [..r-1] are all less than x
     *
     * Without the l = r - 1 step, then [...l] would all be less than or equal to x, losing the two-segment property,
     *           when leftAbs === rightAbs, we can't tell whether to l-- or r++
     *
     * With l == r - 1, we can guarantee [...l] must be less than x, thus having the feasible solution interval (l..r],
     *           when leftAbs === rightAbs, we should l--
     */
    l = r - 1
    while (r - l <= k) {
        const leftAbs = x - arr[l]
        const rightAbs = arr[r] - x
        /** Also need to consider cases where x is not in array index */
        if (l < 0) {
            r++
        } else if (r > arr.length - 1) {
            l--
        } else if (leftAbs <= rightAbs) {
            l--
        } else {
            r++
        }
    }
    return arr.slice(l + 1, r)
}

Once again deepening our understanding of feasible solution intervals 🐶

lc.793 Preimage Size of Factorial Zeroes Function hard

Math problem, really wouldn't know without looking at the answer~

lc.852 Peak Index in a Mountain Array

/**
 * @param {number[]} arr
 * @return {number}
 */
var peakIndexInMountainArray = function (arr) {
    let l = 0,
        r = arr.length - 1
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        if (arr[mid] < arr[mid + 1]) {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return l
}

Is there any difference from lc.162...

lc.875 Koko Eating Bananas

/**
 * @param {number[]} piles
 * @param {number} h
 * @return {number}
 */
var minEatingSpeed = function (piles, h) {
    // Find k, according to problem, k's minimum is 1, maximum is the maximum value in piles
    let max = 0
    for (const num of piles) {
        max = num > max ? num : max
    }
    let l = 1,
        r = max
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        if (getHourWhenSpeedIsMid(piles, mid) > h) {
            l = mid + 1
        } else {
            r = mid // Shrinking right boundary again~
        }
    }
    return l
}
function getHourWhenSpeedIsMid(piles, speed) {
    let hours = 0
    for (const num of piles) {
        hours += Math.ceil(num / speed)
    }
    return hours
}

lc.1011 Capacity To Ship Packages Within D Days

Almost identical to lc.875

var shipWithinDays = function (weights, days) {
    // According to problem, minimum capacity is maximum of weights, maximum capacity is sum of weights
    let l = Math.max(...weights),
        r = weights.reduce((a, b) => a + b)
    while (l < r) {
        const mid = l + ((r - l) >> 1)
        if (getDays(weights, mid) > days) {
            l = mid + 1
        } else {
            r = mid
        }
    }
    return l
}
function getDays(weights, mid) {
    let days = 1
    let count = 0
    for (const weight of weights) {
        count += weight
        if (count > mid) {
            days++
            count = weight
        }
    }
    return days
}

lc.1201 Ugly Number III

This problem also requires mathematical knowledge, really wouldn't know without it 😭 This answer is copied, really opened my eyes

Number of numbers divisible by a in [1..i] is i / a
Inclusion-exclusion principle: Number of numbers divisible by a or b or c in [1..i] = i/a−i/b−i/c−i/ab−i/bc−i/ac+i/abc. Where i/ab represents numbers divisible by both a and b, same for others.

/**
 * @param {number} n
 * @param {number} a
 * @param {number} b
 * @param {number} c
 * @return {number}
 */
var nthUglyNumber = function (n, a, b, c) {
    const ab = lcm(a, b)
    const ac = lcm(a, c)
    const bc = lcm(b, c)
    const abc = lcm(ab, c)
    let left = Math.min(a, b, c)
    let right = n * left
    while (left < right) {
        const mid = Math.floor((left + right) / 2)
        const count =
            low(mid, a) +
            low(mid, b) +
            low(mid, c) -
            low(mid, ab) -
            low(mid, ac) -
            low(mid, bc) +
            low(mid, abc)
        if (count >= n) {
            right = mid
        } else {
            left = mid + 1
        }
    }
    return right
}
function low(mid, val) {
    return (mid / val) | 0
}
function lcm(a, b) {
    //Least common multiple
    return (a * b) / gcd(a, b)
}
function gcd(a, b) {
    //Greatest common divisor
    return b === 0 ? a : gcd(b, a % b)
}

Summary: Once you have a deep understanding of loop invariants and feasible solution intervals, binary search itself has no difficult points. The hard problems above are difficult because they combine binary search with other logic, like greedy and mathematics, so we need to be extremely proficient with binary search itself, treating it as a tool, able to use it naturally when encountering fast search problems where binary search can be applied, peace!