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