如何在按首元素排序的元组列表中高效查找指定元组？

针对已经按元组首元素（id）排序的列表，我们可以用Python内置的bisect模块实现高效的二分查找，替代暴力遍历。以下是两种可行方案：

方案一：Python 3.10+ 版本（支持key参数） #

Python 3.10及以上的bisect模块新增了key参数，可以直接针对元组的首元素进行比较：

import bisect

# 已排序的元组列表
records_by_id = [(0, 'bubble4'), (3, 'bubble5'), (4, 'bubble3'), (5, 'bubble2'), (10, 'bubble1')]
target_id = 4

# 用bisect_left查找目标id的索引
index = bisect.bisect_left(records_by_id, target_id, key=lambda x: x[0])

# 验证目标是否存在（避免id不在列表中的情况）
if index < len(records_by_id) and records_by_id[index][0] == target_id:
    print(f"找到索引：{index}，对应元组：{records_by_id[index]}")
else:
    print("目标id不存在")

方案二：兼容Python 3.10以下版本 #

旧版本bisect不支持key参数，可以先提取所有id生成单独列表，再通过二分查找定位：

import bisect

# 已排序的元组列表
records_by_id = [(0, 'bubble4'), (3, 'bubble5'), (4, 'bubble3'), (5, 'bubble2'), (10, 'bubble1')]
target_id = 4

# 提取所有元组的首元素，生成id列表
id_list = [item[0] for item in records_by_id]
# 在id列表中查找目标id的位置
index = bisect.bisect_left(id_list, target_id)

# 验证目标是否存在
if index < len(records_by_id) and records_by_id[index][0] == target_id:
    print(f"找到索引：{index}，对应元组：{records_by_id[index]}")
else:
    print("目标id不存在")

关键说明 #

• 使用bisect_left而非bisect_right的原因：如果列表中存在重复id，bisect_left会返回第一个匹配元素的索引，符合常规查找需求。
• 必须添加存在性验证：若目标id不在列表中，bisect会返回该id应该插入的位置，此时需要判断该位置的元素id是否与目标一致，避免返回错误索引。

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