记忆 `lower_bound` 和 `upper_bound`（或你实现的 `last_less_equal`）

记忆 lower_bound 和 upper_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_bound 和 upper_bound（标准库）：
  使用 r = mid 或 l = mid + 1，因为目标是找到 第一个 满足条件的位置。

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

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

• lower_bound 和 upper_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_bound、upper_bound 和 last_less_equal 的实现。多加练习和实际应用是巩固记忆的最佳方法！