下界与上界
从零实现 bisect_left 和 bisect_right，然后用它们查找目标值第一次和最后一次出现的位置。
下界与上界 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 3 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
什么是下界和上界？
在有序数组中，目标值的下界是第一个大于或等于目标值的元素的索引（通常称为 bisect_left）。上界是第一个严格大于目标值的元素的索引（bisect_right）。两者共同界定目标值的所有出现位置，并支持 O(log n) 的范围查询。
这两种操作是许多面试题的基础：统计出现次数、查找范围、确定插入位置等。
arr = [1, 2, 2, 2, 3, 5]
# lower bound of 2 => index 1 (first element >= 2)
# upper bound of 2 => index 4 (first element > 2)
# occurrences of 2 => upper - lower = 4 - 1 = 3
print('lower bound of 2:', 1)
print('upper bound of 2:', 4)
print('count of 2:', 4 - 1)实现下界（bisect_left）
bisect_left(arr, x) 返回满足 arr[i] >= x 的最左侧索引 i；如果所有元素都小于 x，则返回 len(arr)。该实现使用不包含上界的边界：hi = len(arr)，循环条件为 lo < hi，并在 arr[mid] >= x 时更新 hi = mid。这样可以确保结果收敛到最左侧的有效位置。
def bisect_left(arr, x):
lo, hi = 0, len(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] < x:
lo = mid + 1
else:
hi = mid # arr[mid] >= x, so potential answer
return lo # lo == hi == insertion point
arr = [1, 2, 2, 2, 3, 5]
print(bisect_left(arr, 2)) # 1
print(bisect_left(arr, 0)) # 0 (before all)
print(bisect_left(arr, 6)) # 6 (after all)
print(bisect_left(arr, 3)) # 4实现上界（bisect_right）
bisect_right(arr, x) 返回满足 arr[i] > x 的最左侧索引 i。它与 bisect_left 的区别只有一行：条件从 arr[mid] < x 改为 arr[mid] <= x。当 arr[mid] <= x 时，结果严格位于 mid 的右侧，因此设置 lo = mid + 1；否则从右侧缩小范围。
def bisect_right(arr, x):
lo, hi = 0, len(arr)
while lo < hi:
mid = lo + (hi - lo) // 2
if arr[mid] <= x:
lo = mid + 1 # arr[mid] <= x, so answer is strictly right
else:
hi = mid
return lo
arr = [1, 2, 2, 2, 3, 5]
print(bisect_right(arr, 2)) # 4
print(bisect_right(arr, 0)) # 0
print(bisect_right(arr, 5)) # 6
print(bisect_right(arr, 4)) # 5使用两个边界统计出现次数
要在 O(log n) 时间内统计目标值在有序数组中的出现次数，同时应用两个边界：count = bisect_right(arr, target) - bisect_left(arr, target)。如果 count 为 0，说明目标值不存在。这比线性扫描快得多，是对有序数据进行频率查询的标准方法。
import bisect
def count_occurrences(arr, target):
left = bisect.bisect_left(arr, target)
right = bisect.bisect_right(arr, target)
return right - left
arr = [1, 2, 2, 2, 3, 3, 5]
print(count_occurrences(arr, 2)) # 3
print(count_occurrences(arr, 3)) # 2
print(count_occurrences(arr, 4)) # 0
print(count_occurrences(arr, 1)) # 1查找目标值的第一个和最后一个位置
LeetCode 34“在有序数组中查找元素的第一个和最后一个位置”要求您在 O(log n) 时间内返回 [first_idx, last_idx]。第一个位置是 bisect_left(arr, target)，但前提是 arr[result] == target。最后一个位置是 bisect_right(arr, target) - 1。如果任一检查失败，则返回 [-1, -1]。
import bisect
def search_range(nums, target):
left = bisect.bisect_left(nums, target)
if left == len(nums) or nums[left] != target:
return [-1, -1]
right = bisect.bisect_right(nums, target) - 1
return [left, right]
print(search_range([5,7,7,8,8,10], 8)) # [3, 4]
print(search_range([5,7,7,8,8,10], 6)) # [-1, -1]
print(search_range([], 0)) # [-1, -1]插入位置（LeetCode 35）
LeetCode 35“搜索插入位置”要求确定：要保持数组有序，目标值应插入到哪里？这正是 bisect_left(arr, target)。如果目标值存在，bisect_left 会返回其索引；如果目标值不存在，bisect_left 会返回它应被插入的索引。无需特殊处理——同一个函数可以处理这两种情况。
import bisect
def searchInsert(nums, target):
return bisect.bisect_left(nums, target)
print(searchInsert([1,3,5,6], 5)) # 2 (exists at index 2)
print(searchInsert([1,3,5,6], 2)) # 1 (would insert between 1 and 3)
print(searchInsert([1,3,5,6], 7)) # 4 (would append at end)
print(searchInsert([1,3,5,6], 0)) # 0 (would prepend)bisect_left 与 bisect_right 的区别
不存在重复值时，bisect_left 和 bisect_right 返回相同的索引。只有当目标值出现多次时，两者的区别才会体现出来。bisect_left 指向第一个副本；bisect_right 指向最后一个副本之后的位置。请始终根据您希望在已有副本之前插入（左侧）还是之后插入（右侧）来选择。
import bisect
arr = [1, 2, 2, 2, 3]
# Insert a new 2 before all existing 2s
print(bisect.bisect_left(arr, 2)) # 1
# Insert a new 2 after all existing 2s
print(bisect.bisect_right(arr, 2)) # 4
# For a value not in array, both give same insertion point
print(bisect.bisect_left(arr, 2.5)) # 4
print(bisect.bisect_right(arr, 2.5)) # 4将边界应用于有序数组的频率查询
当您需要高效回答有序数组中的大量范围频率查询时，可以预先对数组排序一次，并在每次查询中使用二分查找。每个查询都能在 O(log n) 而不是 O(n) 的时间内回答“[lo, hi] 中有多少个元素？”。这种模式常见于排序后统计某个数值范围内元素数量的问题。
import bisect
def count_in_range(arr, lo, hi):
'''Count elements in arr with lo <= val <= hi. arr must be sorted.'''
left = bisect.bisect_left(arr, lo)
right = bisect.bisect_right(arr, hi)
return right - left
arr = sorted([3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5])
print(arr) # [1,1,2,3,3,4,5,5,5,6,9]
print(count_in_range(arr, 3, 5)) # 6 (3,3,4,5,5,5)
print(count_in_range(arr, 1, 2)) # 3 (1,1,2)自定义键二分查找
有时搜索键并不是存储的值本身，而是某个派生属性。Python 的 bisect 模块不直接支持键函数，但您可以在循环中应用键函数，手动进行二分查找。当您需要根据对象的某个属性搜索对象列表时，就会用到这种模式。
# Binary search on a list of (score, name) tuples by score
def lower_bound_by_score(records, min_score):
lo, hi = 0, len(records)
while lo < hi:
mid = lo + (hi - lo) // 2
if records[mid][0] < min_score:
lo = mid + 1
else:
hi = mid
return lo
records = [(50, 'Alice'), (72, 'Bob'), (72, 'Carol'), (88, 'Dave'), (95, 'Eve')]
idx = lower_bound_by_score(records, 72)
print(idx) # 1 (first record with score >= 72)
print(records[idx:]) # [(72,'Bob'),(72,'Carol'),(88,'Dave'),(95,'Eve')]使用边界时常见的面试错误
最常见的错误是在调用 bisect_left 后忘记验证。该函数总会返回有效的插入索引，但不保证该索引处的元素等于目标值。在假定找到目标值之前，请始终检查 arr[result] == target。
第二个错误是在需要查找第一次出现的位置时使用 bisect_right——bisect_right 返回最后一次出现位置之后的位置，因此减去 1 得到的是最后一次出现的位置，而不是第一次。
import bisect
arr = [1, 3, 5, 7]
target = 4
# bisect_left returns 2 (insertion point for 4 between 3 and 5)
idx = bisect.bisect_left(arr, target)
print(idx) # 2
# Validate: arr[2] is 5, not 4 => target absent
found = idx < len(arr) and arr[idx] == target
print('Found:', found) # False总结：何时使用 bisect_left 而不是 bisect_right
当您需要以下结果时使用 bisect_left：目标值第一次出现的位置、会将已有副本移到右侧的插入点，或检查目标值是否存在。当您需要以下结果时使用 bisect_right：最后一次出现位置之后的位置、所有已有副本之后的插入点，或小于或等于目标值的元素数量（它等于 bisect_right(arr, target)）。
两者的运行时间都是 O(log n)，并且都属于 Python 标准库，因此除非面试官要求您从头实现，否则可以直接导入并使用它们。
快速检查
检验您对本课数据结构与算法——编程面试准备相关概念的理解。
课程回顾
本课您学到了：bisect_left 查找第一个 >= target 的元素，bisect_right 查找第一个 > target 的元素（即最后一次出现位置之后的位置），以及两者的差值可以在 O(log n) 时间内得到出现次数。下一节我们将学习答案空间二分查找，此时搜索空间是可能答案的范围，而不是数组索引。
常见问题解答
「下界与上界」课时是免费的吗？
是的 — 「下界与上界」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「下界与上界」这节课中我会学到什么？
从零实现 bisect_left 和 bisect_right，然后用它们查找目标值第一次和最后一次出现的位置。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 3 节课，共 4 节。
「下界与上界」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。