二分法算法总结

例子1:连续数组分组:

题目:例如array = [8, 8, 8, 8], 划分成3个集合,每个集合内的元素必须连续,每个集合内元素总和尽量小,求最大的集合总和。

思路:
输出是最大步长maxSteps 就是每个划分的集合的最大总和
初始值 maxSteps = max(array), sumSteps = sum(array), maxSteps又称为当前step的值,而sumSteps是当前step的上限
通过某种方式,一步一步地缩减maxStep的范围,即削减maxSteps的上限sumSteps,增加maxSteps的下限maxSteps。
极端情况下,最大步长不会超过(maxSteps + sumSteps) >> 1,例如[29, 1], maxSteps = 29, sumSteps = 30, maxStep == 29 + 30 >> 1。
通过这个关系获取maxSteps的候选值steps:(maxSteps + sumSteps) >> 1
找到当前maxSteps的预估值steps的值与划分的集合数的关系。由于数组划分不改变数组的顺序

  • 如果每个集合最大值为steps时,划分的集合数目大于3,说明当前maxSteps的预估值steps的值小了,需要maxSteps = steps + 1
  • 如果每个集合最大值为steps时,划分的集合数目小于3,说明当前maxSteps的预估值steps应该更小,sumStep = steps-1
  • 如果每个集合最大值为steps时,划分的集合数目等于3,说明当前maxSteps的预估值steps可能就是maxSteps的值,sumSteps=steps

  总结:数组分组算法是特殊的二分类算法。

  动态规划和二分法对比:如果可以找到当前结点结果与上一结点结果的关系,用动态规划,如果不能,可以试一试二分法。

原文地址:https://www.cnblogs.com/yulianggo/p/13417988.html