二分搜索中如何判断使用上/下中位数，以及返回lo还是hi？

二分搜索中位数选择与返回值规则 #

1. 上/下中位数的选择（对应while lo < hi模板） #

该模板核心是每次缩小区间时要避免死循环，选择规则完全由分支逻辑决定：

• 若分支逻辑为 满足条件时保留mid作为左边界，不满足时右边界移到mid-1，即：

  if 条件成立:
      lo = mid
  else:
      hi = mid - 1
  

  必须使用上中位数计算mid：mid = (lo + hi + 1) // 2。原因是当lo和hi差1时，不加1计算的下中位数会等于lo，若条件成立会导致lo永远等于原值，进入死循环。
  你给出的缎带问题第一个代码就是该场景：要找最大的有效切割长度，只要mid满足切割要求，比mid小的值必然也满足，因此可以往更大的区间搜索，把lo设为mid保留候选，所以需要用上中位数。

• 若分支逻辑为 满足条件时保留mid作为右边界，不满足时左边界移到mid+1，即：

  if 条件成立:
      hi = mid
  else:
      lo = mid + 1
  

  直接使用下中位数计算mid：mid = (lo + hi) // 2即可，不会触发死循环。该逻辑常用于「找第一个满足条件的最小值」类场景，比如找有序数组中第一个大于等于target的索引。

2. while lo <= hi模板的返回值规则 #

该模板每次判断后都会将mid排除出候选区间，循环结束时必然满足lo = hi + 1，返回值由搜索目标决定：

• 若目标是找最大的满足条件的值：返回hi。因为最后一次满足条件的mid会触发lo = mid + 1，此时hi仍然保留着最后一次有效的mid值，刚好是最大有效值。你给出的缎带问题第二个代码就是该场景，所以返回hi。
• 若目标是找最小的满足条件的值：返回lo。因为最后一次满足条件的mid会触发hi = mid - 1，此时lo仍然保留着最后一次有效的mid值，刚好是最小有效值。

缎带问题逻辑验证 #

以示例输入ribbons = [7,5,9], k = 4为例，总长度为21，最大可能切割长度为21//4=5：

• 上中位数模板运行过程：初始lo=1, hi=5，mid取3满足条件→lo=3；mid取4满足条件→lo=4；mid取5不满足条件→hi=4，循环结束返回lo=4，结果正确。
• 下中位数模板运行过程：初始lo=1, hi=5，mid取3满足条件→lo=4；mid取4满足条件→lo=5；mid取5不满足条件→hi=4，循环结束返回hi=4，结果正确。

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