## Summary

In this post, I will introduce some problems which could binary search the best result.

The problems in this category usually ask for a best value. The value could fall into the range of `[min, max]`

. Another important property is that if the value at the middle is not achievable, we could eliminate a half the range.

A possible solution is that we binary search this best value, and check if it is achievable or not. Repeat until we get a single answer.

## OJ

Trick | Difficulty | |
---|---|---|

LC 644 Maximum Average Subarray II | Binary Search Result + Greedy + Maximum Subarray Sum | 6 points |

LC 410 Split Array Largest Sum | Binary Search Result + Greedy | 6-7 points |

## Details

#### LC 410 Split Array Largest Sum

Given an array which consists of non-negative integers and an integer *m*, you can split the array into *m* non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these *m* subarrays.

The DP solution is not difficult.

```
// alg[n][M] = 0
alg[i][m] =
min{max(alg[j + 1][m - 1], sum[i, ..., j]), for j in [i, ..., n - 1]}
```

The problem could be solved via binary searching the result.

- The minimum value possible is
`min_element(nums)`

; the maximum value possible is`sum(nums)`

- If a value
`mid`

is not possible, it is not possible for values smaller than mid; `check`

could be done in`O(n)`

by greedily dividing groups: from left to right, as long as current sum is smaller than`mid`

, insert it into the current group. If finally`count <= K`

, we know`mid`

is possible, since we could further divide some groups but not increase the largest sum. The tricky part is if`count > K`

, we know all smaller values are not possible. This could be proved by contradiction. If a smaller value is possible, the first subarray would be smaller, so is the second array, which causes the number of subarrays will be not smaller than`count`

, which causes the contradiction.