Advanced Applications of Binary Search
Introduction
In [this post](/posts/abinarysearchtemplate/ “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 whileloop to keep incrementing k
until we find a k
that satisfies the threshold:


Instead of while True
, we can use a forloop 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](/posts/abinarysearchtemplate/ “A Binary Search Template”) here.


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.


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:

