Advanced Applications of Binary Search

post-thumb

Introduction

In [this post](/blog/posts/a-binary-search-template/ “A Binary Search Template”) we have learned how to use binary search to efficiently find an item in an ordered sequence. In this post we’ll explore problems where the search space is not immediately obvious. If for a condition, condition(k) is True implies condition(k+1) is True, then we can apply binary search.

Find the Smallest Divisor Given a Threshold

This LeetCode problem asks us to find the smallest positive integer k such that the sum achieved by dividing every number in nums by k is less than or equal to a given threshold. Note that in this problem division is rounded to the nearest integer greater than or equal to that element. For example: 1/3 = 1.

For example, if nums = [1,2,5,9] and threshold = 6 then our function should return 5 since dividing every number in nums by 5 results in sum = 1+1+2+2 = 2. Note that 5 is the smallest since if k = 4 then the sum would be 1+1+2+3 which exceeds threshold = 6.

A naive approach would be to try all k's. Use a while-loop to keep incrementing k until we find a k that satisfies the threshold:

from math import ceil

def smallest_divisor(nums, threshold):
    k = 1
    while True:
        if within_threshold(nums, threshold, k):
            return k
        k += 1

def within_threshold(nums, threshold, divisor):
    return sum(ceil(n / divisor) for n in nums) <= threshold

Instead of while True, we can use a for-loop which iterates k from 1 to max(nums) since k will not exceed the maximum among nums.

If we apply within_threshold(nums, threshold, k) on every k from 1 to max(nums), we will get [False, False, ..., False, True, ..., True] and our goal is to find the first index of the first True. We can use [binary search](/blog/posts/a-binary-search-template/ “A Binary Search Template”) here.

def smallest_divisor(nums, threshold):
    left, right = 1, max(nums)
    while left < right:
        mid = left + (right - left) // 2
        if within_threshold(nums, threshold, mid):
            right = mid
        else:
            left = mid + 1
    return left

Capacity To Ship Packages Within D Days

In this problem we need to find the least weight capacity K of the ship that will result in all the packages on the conveyor belt being shipped within D days.

Note that the capacity K needs to be at least max(weights), the maximum weight among all weights. The capacity will not exceed sum(weights), the sum of all weights. A brute force approach iterates all values between max(weights) and sum(weights) and returns the first one that satisfies the condition.

def ship_within_days(weights, D):
    for k in range(max(weights), sum(weights) + 1):
        if can_ship_in_time(weights, D, k):
            return k

def can_ship_in_time(weights, days, capacity):
    used = 1
    current = 0
    for w in weights:
        if current + w > capacity:
            current = 0
            used += 1
        current += w
        if used > days:
            return False
    return used <= days

Observe that if all packages can be shipped in time using capacity K, then the packages can also be shipped in time using capacity K + 1, K + 2, etc. So if we apply can_ship_in_time to every capacity from max(weights) to sum(weights), we should have [False,..., False, True, ..., True] and our goal is the find the smallest k such that can_ship_in_time(weights, days, k) evaluates to True. This again can be solved using binary search:

def ship_within_days(weights, D):
    left, right = max(weights), sum(weights)
    while left < right:
        mid = left + (right - left) // 2
        if can_ship_in_time(weights, D, mid):
            right = mid
        else:
            left = mid + 1
    return left

Further Exercises

comments powered by Disqus