This post will introduce one specific application of Binary Search, i.e., when you are asked to find the upper or lower bound, or more precisely, when you need to find the maximum of the smallest value or the minimum of the largest value.
Binary Search is an algorithm to search for a target from a sorted array. It selects the middle element in the array and compares it against the target; if they are not equal, it eliminates one half of the array and keeps searching the other half in the same manner(Wikipedia).
The most basic application of it is to find a number or a position from an array. Some practices could be found on Leetcode:
- 278. First Bad Version
- 33. Search in Rotated Sorted Array
- 34. Find First and Last Position of Element in Sorted Array
- 4. Median of Two Sorted Arrays
Another popular case to apply is when you are asked to find the maximum of the smallest value or the minimum of the largest value. Let’ take 410. Split Array Largest Sum from Leetcode as an example to illustrate how to deal with this kind of problem.
How to search
The search space would be from the maximum of the input
m=len(nums), to the sum of
Each time we would pick the middle element
mid of the search space as our threshold, and calculate the number of subarrays
count while making sure that the sum of each subarray does not exceed
count>m, it means we should increase
mid to reduce the number of subarrays; else if
count<=m, it means we can decrease
mid to increase the number of subarrays, but
mid is still qualified.
So the pseudocode is:
while l < r: mid = l + (r-l)//2 if count(mid) > m: l = mid + 1 else: r = mid return l
How to pick the mid, l, and r
Pick the mid
When picking the mid out of odd number of items, we can find the middle one; when the number of items is even, there are two ways to pick: the former one or the latter one.
Both of them works, but it should align with how we deal with
r. When we select the former one using
l+(r-l)//2, we want to make sure to avoid
l = mid because that might lead to infinite loop. For example when there are two elements
mid and the iteration goes again and again.
Similarly, when we select the latter one using
r-(r-l)//2, we want to avoid
Assigning values to l and f
So shall we assign values to
It depends on the context!
For example, when the question asks for the lower bound, if
mid works, then
r should be
mid might be the answer! And when
mid does not work,
l should be
mid+1 because we are sure the
mid is not the answer and everything falls one
mid‘s left won’t work either.
Similarly, we can assign values to
r as below.
In a word, the way we select
mid and assign values to
r is determined by which we are looking for: lower bound vs. upper bound.
Finally, we need to implement the
count function and here’s the AC code.
class Solution: def splitArray(self, nums: List[int], m: int) -> int: l,r,n = max(nums),sum(nums),len(nums) def count(target): ret = cur = 0 for num in nums: if cur+num > target: ret += 1 cur = num else: cur += num return ret + 1 while l < r: mid = l + (r-l)//2 if count(mid) > m: l = mid + 1 else: r = mid return l
You may find the following practices in the Leetcode: