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