二分查找寻找一个有序边界。把目标从“找到某个相等元素”改成“找到第一个不小于目标的位置”，空数组、重复值和找不到目标就能共享同一套定义。
一个区间约定贯穿全过程
维护未确定区间 [lo, hi)：lo 左侧全部小于目标，hi 及其右侧全部不小于目标。初始 lo=0, hi=len(values)，两侧都是空区间，性质成立。检查中点，若值太小，中点和左侧都可排除；否则中点仍可能是答案，因此只把 hi 移到中点。
def lower_bound(values, target):
lo, hi = 0, len(values)
while lo < hi:
mid = (lo + hi) // 2
if values[mid] < target:
lo = mid + 1
else:
hi = mid
return lo
def minimum_capacity(weights, days):
if days <= 0 or any(w <= 0 for w in weights):
raise ValueError('days and weights must be positive')
if not weights:
return 0
def feasible(capacity):
used, load = 1, 0
for weight in weights:
if load + weight > capacity:
used += 1
load = 0
load += weight
return used <= days
lo, hi = max(weights), sum(weights)
while lo < hi:
mid = (lo + hi) // 2
if feasible(mid):
hi = mid
else:
lo = mid + 1
return lo
if __name__ == '__main__':
print(lower_bound([1, 3, 3, 6], 3))
print(minimum_capacity([3, 2, 2, 4], 2))
循环结束时 lo==hi，未知区间为空，边界就是 lo。每轮严格缩小区间且大约减半，所以比较次数 O(log n)，额外空间 O(1)。函数要求输入已按升序排好；检查有序性本身需 O(n)，不能把这个成本藏进“二分是对数时间”的结论。
对 [1,3,3,6] 查找3返回1，查找8返回4。返回 len(values) 是合法的插入点，解引用之前必须检查边界。若需要上边界，可找第一个严格大于目标的位置；重复值个数就是右边界减左边界。
在答案空间中二分
假设包裹必须按原顺序分天运输，一天能运输的总重量不超过容量。容量越大，所需天数不会增加，因此“能否在D天内完成”是单调谓词。答案可在“最大单件重量”与“全部重量之和”之间二分，判定函数每次扫描一遍包裹，总成本 O(n log S)，S表示候选容量区间的宽度。
单调性要证明，不能因为答案是数字就二分。若加入每天随机限时或费用折扣，容量与目标的关系可能改变。整数边界二分会精确终止；浮点二分要单独指定迭代次数或误差模型，不能依赖 lo==hi。
常见错误
hi=mid-1 与当前半开区间约定不一致，可能跳过答案；lo=mid 在只有两个候选位置时可能不前进。另一种闭区间写法也可以正确，但不能混用其更新规则。
Python 的 bisect_left 与这里的边界语义相同。插入点查找 O(log n)，真正调用列表插入仍需搬移元素，通常 O(n)。并发修改序列会破坏有序前提，应先明确数据快照或同步方式。
练习与面试自查
实现右边界与闭区间 [left,right] 的计数查询，使用空数组、全部相等、目标在两侧和单元素测试。再为运输问题写朴素枚举容量的基线。面试中先说区间含义、单调谓词和退出条件，再写更新语句，能直接解释为什么不会死循环或遗漏最后一个候选。
本地运行
示例仅使用 Python 标准库，适用于 Python 3.10 及以上。把 example.py 与 test_example.py 保存到同一个目录，在该目录运行：
python example.py
python -m unittest -v test_example.py
测试检查本文列出的边界；新增练习仍需自己补充断言。