You have 2 free member-only stories left this month.
This is originally posted at https://shawnlyu.com/algorithms/binary-search-find-upper-and-lower-bound/
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
Search space
The search space would be from the maximum of the input nums, when m=len(nums), to the sum of nums, when m=1.
Search strategy
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 mid. If 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 lHow 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 l and 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 [0,1] and mid=0, then lbecomes mid and the iteration goes again and again.
Similarly, when we select the latter one using r-(r-l)/2, we want to avoid r=mid.
Assigning values to l and f
So shall we assign values to l and r?
It depends on the context!
Lower bound
For example, when the question asks for the lower bound, if mid works, then r should be mid not mid-1 because 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.
Upper bound
Similarly, we can assign values to l and r as below.
In a word, the way we select mid and assign values to l and 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 lPractices
You may find the following practices in the Leetcode:
