记忆 `lower_bound` 和 `upper_bound`(或你实现的 `last_less_equal`)

发布于:2025-03-17 ⋅ 阅读:(14) ⋅ 点赞:(0)

记忆 lower_boundupper_bound(或你实现的 last_less_equal)函数的关键在于理解它们的行为和二分查找的逻辑。以下是一些记忆方法和技巧:


1. 理解函数的行为

  • lower_bound
    返回 第一个不小于目标值的位置
    记忆:“下界”,即目标值的下限(第一个 ≥ 目标值的位置)。

  • upper_bound(标准库):
    返回 第一个大于目标值的位置
    记忆:“上界”,即目标值的上限(第一个 > 目标值的位置)。

  • last_less_equal(你实现的 upper_bound):
    返回 最后一个小于或等于目标值的位置
    记忆:“最后一个 ≤ 目标值的位置”


2. 记忆二分查找的条件

二分查找的核心是 if 条件,它决定了搜索范围的移动方向。可以通过以下方式记忆:

lower_bound 的条件:
if (a[mid] >= target) r = mid;
else l = mid + 1;
  • 记忆:“找第一个 ≥ 目标值的位置”,所以当 a[mid] >= target 时,向左移动右边界。
upper_bound(标准库)的条件:
if (a[mid] > target) r = mid;
else l = mid + 1;
  • 记忆:“找第一个 > 目标值的位置”,所以当 a[mid] > target 时,向左移动右边界。
last_less_equal 的条件:
if (a[mid] <= target) l = mid;
else r = mid - 1;
  • 记忆:“找最后一个 ≤ 目标值的位置”,所以当 a[mid] <= target 时,向右移动左边界。

3. 记忆边界更新方式

  • lower_boundupper_bound(标准库)
    使用 r = midl = mid + 1,因为目标是找到 第一个 满足条件的位置。

  • last_less_equal
    使用 l = midr = mid - 1,因为目标是找到 最后一个 满足条件的位置。


4. 记忆二分查找的取整方式

  • lower_boundupper_bound(标准库)
    使用 mid = l + (r - l) / 2(向下取整),因为目标是找到 第一个 满足条件的位置。

  • last_less_equal
    使用 mid = l + (r - l + 1) / 2(向上取整),因为目标是找到 最后一个 满足条件的位置。


5. 记忆模板

将函数的行为和实现模板化,方便记忆:

lower_bound 模板:
int lower_bound(int a[], int n, int target) {
    int l = 0, r = n - 1;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] >= target) r = mid; // 向左移动
        else l = mid + 1;              // 向右移动
    }
    return l; // 返回第一个 >= target 的位置
}
upper_bound(标准库)模板:
int upper_bound(int a[], int n, int target) {
    int l = 0, r = n - 1;
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] > target) r = mid; // 向左移动
        else l = mid + 1;             // 向右移动
    }
    return l; // 返回第一个 > target 的位置
}
last_less_equal 模板:
int last_less_equal(int a[], int n, int target) {
    int l = 0, r = n - 1;
    while (l < r) {
        int mid = l + (r - l + 1) / 2; // 向上取整
        if (a[mid] <= target) l = mid; // 向右移动
        else r = mid - 1;              // 向左移动
    }
    return l; // 返回最后一个 <= target 的位置
}

6. 记忆口诀

  • lower_bound
    “找第一个 ≥ 目标值,向左移动右边界”

  • upper_bound(标准库)
    “找第一个 > 目标值,向左移动右边界”

  • last_less_equal
    “找最后一个 ≤ 目标值,向右移动左边界”


7. 实际应用练习

通过实际应用加深记忆,例如:

  • 在有序数组中查找某个值的范围。
  • 在有序数组中查找插入位置。
  • 统计某个值的出现次数。

总结

通过理解函数的行为、记忆二分查找的条件和边界更新方式,以及通过模板和口诀进行强化,可以有效地记忆 lower_boundupper_boundlast_less_equal 的实现。多加练习和实际应用是巩固记忆的最佳方法!