为何该二分搜索函数下界取max(A)而非最小值？代码边界疑问解析

哦，你肯定是把这个二分搜索和常规的「在有序数组里找元素」的场景搞混啦！这个函数解决的是**「分割数组，让每块和的最大值尽可能小」**的经典优化问题，属于二分搜索的“非常规”应用，我给你掰扯清楚：

先搞懂上下界的逻辑： #

• 下界lower_bound = max(A)：
  不管你怎么分割数组，每一块至少得装一个元素吧？那分割后每块的和的最大值，最小也不可能比数组里的最大元素还小——毕竟那个最大元素单独成块的话，它的和就是自己，要是候选值比它小，这一块就不满足“和≤候选值”的要求了。比如数组是[3,1,4,2]，最大元素是4，你绝对没法把分割后的每块和都压到4以下，因为4自己就得占一块，和就是4。所以这是我们要找的“最小最大值”的底线。

• 上界upper_bound = sum(A)：
  要是只把数组分成1块（完全不分割），那这一块的和就是数组总和，这是分割后每块和的最大值的天花板——毕竟再怎么分割，最大值也不可能超过整个数组的和对吧？

再看代码里的两个边界判断： #

• 当max_block_cnt == 1：只能分成1块，直接返回总和就行，刚好对应上界的情况。
• 当max_block_cnt >= len(A)：可以给每个元素单独分一块，这时候每块和的最大值就是数组里的最大元素，刚好对应下界的情况。

举个例子更直观： #

比如数组A = [1,2,3,4,5]，要分割成3块：

• 初始下界是5，上界是15
• 先试中间值10：能不能分成3块，每块和不超过10？当然可以——比如[1,2,3]（和6）、[4]（和4）、[5]（和5），都满足。那我们可以尝试找更小的候选值。
• 继续二分下去，最后会找到最小的那个满足条件的最大值（这里是6）。

总结下：这个二分搜索不是找元素，而是在「可能的最大值范围」里，通过二分快速找到满足分割条件的最小最大值，而max(A)和sum(A)刚好是这个范围的合理边界。

内容的提问来源于stack exchange，提问作者Jay Jung