当前位置：首页 > news >正文

详细介绍：二分查找边界模板：第一个＞ target / 第一个＜ target（找不到就返回边界）

news 2026/3/26 19:38:06

详细介绍：二分查找边界模板：第一个＞ target / 第一个＜ target（找不到就返回边界）

二分查找边界模板：第一个 > target / 第一个 < target（找不到就返回边界）

写二分最容易错的不是“能不能找到”，而是 边界怎么收、mid 怎么取、以及找不到时返回什么。这篇把两个常用的“边界型二分”整理成可直接套用的模板。

本文假设数组 a 在区间 [l, r] 内 单调非降（升序可重复）。

1）第一个 `> target` 的下标（upper_bound）

语义

在 a[l..r] 中找最左的下标 idx 满足：

a[idx] > target

如果不存在（也就是全都 <= target），返回边界 r（夹到右边界）。

说明：经典 upper_bound 不存在时返回 r+1，但你要求“查不到就返回边界”，这里做了“夹边界”处理。

模板（Java）

// 第一个 > target；如果不存在，返回 r（右边界）
static int firstGreaterOrRight(int[] a, int l, int r, int target) {
int lo = l, hi = r + 1; // 搜索落点允许到 r+1（虚拟位置，不访问数组）
while (lo < hi) {
int mid = lo + ((hi - lo) >>> 1);
if (a[mid] > target) hi = mid;
else lo = mid + 1;
}
// lo 是“第一个 > target”的位置，可能是 r+1
return (lo == r + 1) ? r : lo;
}

关键点

hi = r+1 是“虚拟位置”，不会访问 a[r+1]，因为 mid < hi，所以 mid 最大只会到 r。
最后 lo 可能为 r+1，表示不存在，于是按需求返回 r。

2）第一个 `< target` 的下标（最左的“小于”）

语义

在 a[l..r] 中找最左的下标 idx 满足：

a[idx] < target

如果不存在（也就是全都 >= target），返回边界 l（夹到左边界）。

注意：这不是“最后一个 < target”，而是“第一个 < target”（最左的小于）。

模板（Java）

思路：
“第一个 < target” 等价于在单调数组中找 第一个 >= target 的位置 lb（lower_bound），那么答案就是：

如果 lb == l：说明没有 < target，按需求返回 l
否则：最左 < target 就是 l（因为 lb 之前都 < target，最左必然是 l）

但这推导对“最左”很尴尬：只要存在 < target，最左一定是 l。
所以更有用、也更符合你想表达“边界二分”的，通常写的是：

✅ 第一个 >= target（lower_bound）
或 ✅ 最后一个 < target

你这里写“第一个小于target”很可能是口误，实际想要的是“最后一个小于 target”。我直接给你三者都放上，博客更完整，也不坑你。

2A）第一个 `>= target`（lower_bound，强烈推荐你用这个）

语义

找最左 idx 满足 a[idx] >= target
不存在时返回 r（夹到右边界）

// 第一个 >= target；如果不存在，返回 r
static int firstGeOrRight(int[] a, int l, int r, int target) {
int lo = l, hi = r + 1;
while (lo < hi) {
int mid = lo + ((hi - lo) >>> 1);
if (a[mid] >= target) hi = mid;
else lo = mid + 1;
}
return (lo == r + 1) ? r : lo;
}

2B）最后一个 `< target`（更常用，且和“第一个 >”对偶）

语义

找最右 idx 满足 a[idx] < target
不存在时返回 l（夹到左边界）

// 最后一个 < target；如果不存在，返回 l
static int lastLessOrLeft(int[] a, int l, int r, int target) {
int lo = l - 1, hi = r;   // lo 允许落到 l-1（虚拟位置，不访问数组）
while (lo < hi) {
int mid = lo + ((hi - lo + 1) >>> 1); // 上中位数，避免死循环
if (a[mid] < target) lo = mid;
else hi = mid - 1;
}
// lo 可能是 l-1 表示不存在
return (lo == l - 1) ? l : lo;
}

3）为什么“虚拟边界”不会越界？

在 hi = r+1 的模板里，mid 永远满足 mid < hi，因此 mid <= r，不会访问 a[r+1]
在 lo = l-1 的模板里，我们用 上中位数，保证 mid >= lo+1 >= l，不会访问 a[l-1]

4）一眼记住的对偶关系

需求	典型模板	可能的“找不到”落点	按本文“夹边界”返回
第一个 `> target`	`hi = r+1`，mid 下取	`r+1`	`r`
第一个 `>= target`	`hi = r+1`，mid 下取	`r+1`	`r`
最后一个 `< target`	`lo = l-1`，mid 上取	`l-1`	`l`