Advanced Applications of Binary Search
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
- Minimum Number of Days to Make m Bouquets
- Koko Eating Bananas
- Ugly Number III
- Missing Element in Sorted Array
Related Posts
- Leetcode 424 - Longest Repeating Character Replacement
- Two Sum and Its Variants
- Leetcode 1004 - Max Consecutive Ones III
- Leetcode 222 - Count Complete Tree Nodes
- Leetcode 1027 - Longest Arithmetic Subsequence
- Question 1299 on leetcode
- Leetcode 240 - Search a 2D Matrix II
- Leetcode 1351 - Count Negative Numbers in a Sorted Matrix
- Leetcode 239 - Sliding Window Maximum
- Leetcode 209 - Minimum Size Subarray Sum
- LeetCode 230 - Kth Smallest Element in a BST with Code
- Leetcode 96 - Unique Binary Search Trees
- Leetcode 540 - Single Element in a Sorted Array
- Leetcode 1283 - Find the Smallest Divisor Given a Threshold
- Leetcode 74 - Search a 2D Matrix
- Leetcode 300 - Longest Increasing Subsequence
- Leetcode 930 - Binary Subarrays With Sum
- Blazingly fast solution to LeetCode #1342 - Number of Sub-arrays of Size K and Average Greater than or Equal to Threshold (Cross-post from r/SoftwareEngineering)
- Leetcode 704 - Binary Search
- Leetcode 643 - Maximum Average Subarray I
- LeetCode - Two Sum Solution with Code
- a-binary-search-template
- Leetcode 1358 - Number of Substrings Containing All Three Characters
- Leetcode 33 - Search in Rotated Sorted Array
- Leetcode 1151 - Minimum Swaps to Group All 1’s Together