# Advanced Applications of Binary Search

☰ Table of Content

### Introduction

In [this post](/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:

 `````` 1 2 3 4 5 6 7 8 9 10 11 `````` ``````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](/posts/a-binary-search-template/ “A Binary Search Template”) here.

 ``````1 2 3 4 5 6 7 8 9 `````` ``````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.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 `````` ``````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:

 ``````1 2 3 4 5 6 7 8 9 `````` ``````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

Update: 2021-10-19