Binary Search
- The idea is quite simple but difficult to write bug-free implementation code in just a few minutes
- When to exit the loop? Should we use
left < right
orleft <= right
as the while loop condition? - How to initialize the boundary variable
left
andright
? - How to update the boundary? How to choose the appropriate combination from
left= mid
,left = mid + 1
, andrigth = mid
,right = mid - 1
- When to exit the loop? Should we use
- Another misunderstanding of binary search is that people often think this technique could only be used in simple scenario like given a sorted array, find a specific value in it => Can be applied to much more complicated situations.
Template
def binary_search(array) -> int:
def condition(value) -> bool:
pass
left, right = min(search_space), max(search_space) # could be [0, n], [1, n] etc. Depends on problem
while left < right:
mid = left + (right - left) // 2
if condition(mid):
right = mid
else:
left = mid + 1
return left
- When using this template, we only need to modify three parts
- Correctly initialize
left
andright
to specify search space. One rule is to setup the boundary to include all possible elements - Decide return values. Is it
return left
orreturn left - 1
? Remember this: after exiting the while loop,left
**is the minimal k satisfying thecondition
function. - Design
condition
function.
- Correctly initialize
Idea
- Most of the time, the problem is not just find a target number in a sorted array. In this case the sorted array is a search space and target number is the search target. In some problem the search space and search target is not so readily available. => Have to correctly find and declare the search space and search target for binary search to work.
- When can we use binary search? => If we can discover some kind of monotonicity, e.g if condition(k) is True then condition(k+1) is True then we can consider binary search
Example
https://leetcode.com/problems/capacity-to-ship-packages-within-d-days/
- Idea:
- We are given an array of weights and a day limit
- We might automatically treat weights as search space
- The way to look at this problem is
- We are looking at the minimal one among many feasible capacities. If we can successfully ship all packages within
D
days with capacitym
, then we can definitely ship them all with any capacity larger thanm
. - We can design a
condition
function, given an inputcapacity
, it returns whether it's possible to ship all packages withinD
days. This is just a regular function with a for loop. - In this case the search space is the
capacity
, where minimum ismax(weights)
as it has to be able to ship the heaviest package, and maximum issum(weights)
as if the capacity issum(weight)
we can ship all packages in one day.
- We are looking at the minimal one among many feasible capacities. If we can successfully ship all packages within
- Now we can apply the template
def shipWithinDays(weights: List[int], D: int) -> int:
def feasible(capacity) -> bool:
days = 1
total = 0
for weight in weights:
total += weight
if total > capacity: # too heavy, wait for the next day
total = weight
days += 1
if days > D: # cannot ship within D days
return False
return True
left, right = max(weights), sum(weights)
while left < right:
mid = left + (right - left) // 2
if feasible(mid):
right = mid
else:
left = mid + 1
return left