算法推演与练习

前置：能阅读整数数组、比较操作与循环，理解半开区间 [lo,hi)；Python 3.10+ 仅供手推或自跑完整下界程序。教学范围为比较模型；Python 3.10+；半开区间。核对日期2026-10-17。示例未执行，本轮没有安装依赖、生成协议代码、启动服务或浏览器预览。完整源码和输入文件见下方「同源完整文件」；推演结论只适用于写明的模型。

完整下界程序

完整下界程序读取包含values与target的JSON，重复值返回最左匹配的下界。输入校验拒绝布尔值、无序数组和非整数；算法核心与输入防线分开，以便证明核心不变量而不掩盖验证成本。

下界预期与失败

输入处理和二分核心要分别验收。合法有序输入进入查找后，返回的是插入位置，可能等于长度；只有额外验证该位置的值等于 target，才能回答“是否找到”。下面把正常重复值、越界插入点与拒绝输入放在同一条处理路径中。

查看图表代码

下界预期与失败可手推：数组[1,3,3,8]目标3时插入位置为1，目标9时为4，空数组时为0。错误输入[3,1]在查找前拒绝，不能接受一个碰巧正确的下标作为无序输入也能工作的证据。

二分边界练习

二分边界练习要求对[2,2,2]与目标2逐次列出lo、hi和中点，说明为什么hi=mid可以收缩，而lo=mid可能停滞。然后把条件改成第一个大于目标，解释比较符号改变后维护的分区含义。

同源完整文件

以下README含前置、输入、读者自跑步骤、预期结果、失败、恢复与清理；只做静态核对，没有执行。

model.py

import json
import sys

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

def solve(data):
    if not isinstance(data, dict):
        raise ValueError('input must be an object')
    values, target = data.get('values'), data.get('target')
    if not isinstance(values, list) or any(type(x) is not int for x in values):
        raise ValueError('values must be an integer array')
    if type(target) is not int:
        raise ValueError('target must be an integer')
    if any(a > b for a, b in zip(values, values[1:])):
        raise ValueError('values must be sorted')
    index = lower_bound(values, target)
    return {'index': index, 'found': index < len(values) and values[index] == target}

if __name__ == '__main__':
    try:
        print(json.dumps(solve(json.load(sys.stdin))))
    except (ValueError, TypeError) as error:
        print(str(error), file=sys.stderr)
        sys.exit(2)

requirements.txt

# Python 3.10+ standard library only; no third-party dependency.

README.md

# 算法与数据结构：完整示例

示例未执行。核对日期2026-10-17。教学版本族：比较模型；Python 3.10+；半开区间。

## 文件与依赖

文件：model.py, requirements.txt。requirements.txt为同源依赖声明；所有代码和配置都随本文展示。本例使用 Python 3.10+ 标准库，无额外运行依赖。

## 输入与前置

前置：能阅读整数数组、比较操作与半开区间。使用 Python 3.10+，本例只依赖标准库。输入为含 values 和 target 的 JSON 对象；values 必须是有序整数数组，具体输入和预期见下节。

读者将来自跑（本轮未执行）：在本目录以Python 3.10+读取input.json，PowerShell示意`Get-Content -Raw input.json | python model.py`；Bash示意`python3 model.py < input.json`。把下面输入手工保存为UTF-8文件，输出按预期逐项比较。无需安装依赖，没有服务或网络调用；程序只读标准输入并写标准输出，不改原文件。失败信息写标准错误且退出2。恢复是修正输入后重读，清理只删除自己创建的input.json与输出文件，勿递归删除工作目录。

## 预期结果、失败与恢复

输入 {"values":[1,3,3,8],"target":3}；预期 {"index":1,"found":true}。目标9预期index=4且found=false；空数组同理index=0。无序输入退出2，错误文字values must be sorted。

失败要保留输入和错误，先与正文的不变量及边界核对。没有真实服务或性能验证，不以这些模型输出证明生产可用性。

## 独立练习

手推[2,2,2]目标2；再设计upper_bound返回第一个大于目标的位置。

参考答案：初始(0,3)，mid=1令hi=1；随后mid=0令hi=0，返回0。upper_bound仅把“小于目标”改为“小于等于目标”，左区变为所有值不大于目标；两步后返回3，重复值不会跳错。

先作答，再核对

手推[2,2,2]目标2；再设计upper_bound返回第一个大于目标的位置。

逐步参考解答

初始(0,3)，mid=1令hi=1；随后mid=0令hi=0，返回0。upper_bound仅把“小于目标”改为“小于等于目标”，左区变为所有值不大于目标；两步后返回3，重复值不会跳错。

来源与适用边界

• 英文官方、作者或规范原文：本专题机制依据；按上述固定版本族阅读。
• 中文官方或作者资料：用于术语和讲解交叉核对，冲突以原始规范为准。