# Binary Search the Result

## 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

TrickDifficulty
LC 644 Maximum Average Subarray IIBinary Search Result + Greedy + Maximum Subarray Sum6 points
LC 410 Split Array Largest SumBinary Search Result + Greedy6-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.

1. The minimum value possible is `min_element(nums)`; the maximum value possible is `sum(nums)`
2. If a value `mid` is not possible, it is not possible for values smaller than mid;
3. `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.