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 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 `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 `l`

becomes `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 l
```

## Practices

You may find the following practices in the Leetcode: