ex10 二分查找

要学习的知识点

二分查找的有序前提
左闭右开区间
中间下标计算
寻找重复值的第一次位置
边界与不存在情况

题目

练习 10：在递增列表中用二分查找目标值第一次出现的位置（从 0 开始）。

输入：第一行 n，第二行 n 个递增整数，第三行目标值 x。

参考程序：ex10.py；空白练习：lx10.py。

完整代码

以下内容与 ex10.py 一致，可对照右侧讲解阅读。

"""练习 10：在递增列表中用二分查找目标值第一次出现的位置（从 0 开始）。
输入：第一行 n，第二行 n 个递增整数，第三行目标值 x。

学习说明：
- 二分查找要求列表已经升序排列；每轮把可能范围缩小约一半。
- [left, right) 是左闭右开区间；middle 是当前中间下标。
- 若中间值小于 target，答案只能在右半边；否则保留中间及左侧，继续找第一次出现的位置。
- 循环结束时 left 是第一个不小于 target 的位置；再检查它是否真的等于 target。
- 输出的下标从 0 开始；列表中找不到目标时输出 -1。
"""
n = int(input())
values = list(map(int, input().split()))[:n]
target = int(input())

left, right = 0, n
while left < right:
    middle = (left + right) // 2
    if values[middle] < target:
        left = middle + 1
    else:
        right = middle

if left < n and values[left] == target:
    print(left)
else:
    print(-1)

进阶写法

这版与初学版解决同一道题，使用更精炼的语法或标准库工具。

进阶源码：ex10_adv.py

"""练习 10 进阶版：使用 bisect_left 查找有序列表中目标的第一个位置。"""
from bisect import bisect_left

n = int(input())
values = list(map(int, input().split()))[:n]
target = int(input())

position = bisect_left(values, target)
print(position if position < n and values[position] == target else -1)

bisect_left() 在已排序列表中返回目标值可插入的最左位置；再检查该位置是否等于目标，便能处理未找到和重复值。

运行结果

示例输入：

6
2 4 4 4 7 9
4

程序输出：

逐个认识函数

下表根据程序中实际调用的函数和方法整理；自定义函数的实现与算法细节见后续说明。

函数形式	功能与返回值	注意事项
`input(prompt='')`	读取一行文本，返回 str；若提供 prompt 会先显示提示。	返回值默认是字符串，计算前通常要做类型转换。
`str.split(sep=None)`	按分隔符拆分字符串，返回字符串列表。	默认按连续空白拆分并忽略首尾空白。
`int(value, base=10)`	把整数文本或数值转换为整数。	int('3.5') 不合法；按指定进制解析时可传 base。
`list(iterable=())`	从可迭代对象创建列表。	列表有顺序、可修改，允许重复元素。
`map(function, iterable)`	逐个应用函数，返回惰性迭代器。	常与 list() 一起使用以立即取得结果。
`print(*objects, sep=' ', end='\n')`	把对象转换为文本显示；返回 None。	默认空格分隔并在末尾换行。

原理：猜中间，扔掉不可能区域

列表升序排列。若中间值小于目标，左边和中间都不可能是答案；若中间值大于或等于目标，答案可能在左边，也可能就是中间。因此本程序使用“寻找第一个不小于目标的位置”的策略。

把搜索范围设为左闭右开区间 [left, right)，初始为 [0,n)。
取中间下标 middle = (left + right) // 2。
若 values[middle] < target，令 left = middle+1。
否则令 right = middle，保留中间位置及其左侧。
范围空了以后，left 是第一个可能的位置；检查列表里是否确实存在目标。

每轮约把候选范围减半。n 个元素大约需要 log₂(n) 轮，而线性查找最坏要检查 n 个。

关键函数与语法

写法	参数 / 返回值	用途
`input()`	无必需参数，返回输入字符串。	分别读取 n、列表文本和目标值。
`split()`	字符串方法；默认按空白拆分，返回字符串列表。	拆出每个列表数字。
`map(int, iterable)`	逐项转换，返回 map 对象。	配合 list() 得到整数列表。
`list(...)`	将可迭代对象变成列表。	便于按下标访问中间项。
`values[:n]`	列表切片返回一个新列表，包含下标 0 到 n-1 的元素。	程序用切片限制实际读入列表长度，不改变原 values 对象；要求输入的 n 与数据数量相符。
`//` 与下标访问	`//` 是整除；`values[i]` 取列表下标 i 的元素。	要保证每次 middle 都小于 right，才能安全访问。

边界为何是右开

右端 right 不包含在范围中，因此区间长度是 right-left。若 left==right，表示没有候选项。更新 right=middle 而不是 middle-1，使“第一个满足条件的位置”不会被过早丢弃。

二分查找的前提是列表有序。重复值需要找第一次出现时，命中后仍不能立刻结束，要继续往左找。

试一试目标小于所有元素、等于最后一个、重复出现、完全不存在、空列表 n=0。

代码如何运行

先按左侧题目给出的格式输入数据；程序通过 input() 读取，并在需要时转换数据类型。
程序自上而下执行语句；遇到条件、循环或函数调用时，按照右侧算法说明更新变量和处理数据。
最后由 print() 输出计算结果。可将左侧示例输入与输出逐项对照。

先自己跟踪一组小数据，记录循环前后变量的值；这比只看最终答案更容易理解程序。

自己动手试一试

测试目标在开头、末尾、不存在、重复多次，以及空列表；确认重复值返回第一次位置。

先在 lx10.py 中独立完成，再运行参考程序比较结果。修改程序时一次只改一个条件或步骤。