二分查找：用循环不变式守住边界

问题与前提

在非递减数组中，找目标第一次出现的位置；不存在时返回应该插入的位置，也称 lower bound。二分查找要求有序，不能直接用于未排序数组。

半开区间的实现

维护 $[lo,hi)$，初始为 $[0,n)$。不变式是索引小于 $lo$ 的值都小于目标；索引大于等于 $hi$ 的值都大于等于目标。

def lower_bound(values, target):
    lo, hi = 0, len(values)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if values[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo

values = [1, 2, 2, 5]
assert lower_bound(values, 2) == 1
assert lower_bound(values, 3) == 3
assert lower_bound(values, 0) == 0
assert lower_bound(values, 9) == 4
assert lower_bound([], 1) == 0

更新与正确性证明

若中点值小于目标，有序性使所有不大于中点的元素都可排除，所以 lo = mid + 1。否则中点本身可能是答案，应保留，用 hi = mid。两种更新均保持不变式，并严格缩短区间。

循环有限步终止于 $lo=hi$。此时前面元素都小于目标，后面元素都大于等于目标，所以该位置恰是所求下界，或为数组长度 $n$。

检查目标是否存在

import bisect

def contains(values, target):
    index = bisect.bisect_left(values, target)
    return index < len(values) and values[index] == target

assert contains([1, 2, 2, 5], 2)
assert not contains([1, 2, 2, 5], 3)
assert not contains([], 1)

标准库 bisect_left 实现同一语义。先检查索引不越界，再访问数组；and 的短路求值保护空数组与末尾位置。

复杂度与练习

数组支持常数时间随机访问时，每轮至多约减半，时间 $O(\log n)$，额外空间 $O(1)$。若查找前还要排序，应计入排序成本。

练习：实现 upper bound，返回第一个严格大于目标的位置。把判断改为 values[mid] <= target。使用空数组、[2,2,2] 和大于全部元素的目标检查边界。