三个二分模板有何区别，为什么有些题能用有些题不能用？

Question

今天写二分的时候发现有些题用第三个模板能ac，用前面两个不行，只能对一部分，这是为什么呢？第三个模板和前面两个有什么区别？什么题的时候用第三个什么题的时候用前两个呢？
比如这个就是用第三个能ac但是用前两个不能ac：https://www.luogu.com.cn/problem/P1676

Answer 1

让【宝码香车】来帮你解答，本回答参考DeepSeek编写，并整理提供，如果还有疑问可以点击头像关注私信或评论。

如果答案让您满意，请采纳、关注，非常感谢！

---

二分查找是一种高效的查找算法，通常用于在有序数组中查找目标值。二分查找的实现有多种模板，常见的三种模板分别是：

1. 模板一：标准的二分查找模板，适用于查找目标值的精确匹配。
2. 模板二：查找第一个大于等于目标值的元素。
3. 模板三：查找最后一个小于等于目标值的元素。

模板一：标准二分查找

def binary_search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

这个模板适用于查找目标值的精确匹配，如果目标值存在则返回其索引，否则返回-1。

模板二：查找第一个大于等于目标值的元素

def lower_bound(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] >= target:
            right = mid - 1
        else:
            left = mid + 1
    return left

这个模板适用于查找第一个大于等于目标值的元素，返回其索引。如果所有元素都小于目标值，则返回数组长度。

模板三：查找最后一个小于等于目标值的元素

def upper_bound(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] <= target:
            left = mid + 1
        else:
            right = mid - 1
    return right

这个模板适用于查找最后一个小于等于目标值的元素，返回其索引。如果所有元素都大于目标值，则返回-1。

区别与应用场景

1. 模板一适用于精确查找目标值的情况，例如在有序数组中查找某个特定值。
2. 模板二适用于查找第一个大于等于目标值的元素，常用于查找插入位置或查找满足某种条件的最小值。
3. 模板三适用于查找最后一个小于等于目标值的元素，常用于查找满足某种条件的最大值。

为什么有些题用第三个模板能AC，用前两个不行？

这是因为不同的题目要求不同。例如，题目可能要求找到最后一个满足条件的元素，而不是第一个。在这种情况下，模板三（查找最后一个小于等于目标值的元素）会更合适。

以你提到的题目 P1676 为例，题目可能要求找到最后一个满足条件的元素，因此使用模板三可以正确解决问题，而使用模板一或模板二则无法满足题目的要求。

总结

• 模板一：精确查找目标值。
• 模板二：查找第一个大于等于目标值的元素。
• 模板三：查找最后一个小于等于目标值的元素。

根据题目的具体要求选择合适的模板，才能正确解决问题。