全网最全！二分查找的两种核心模板详解

一、先搞懂两个经典场景

我们先看两个最常见的二分查找问题，帮你直观理解需求差异。

场景 1：查找最后一个 ≤ x 的元素

目标：在数组 [1, 2, 3, 5, 5, 5, 7, 8] 中，找到最后一个 ≤ 5 的数的下标。

数组里有多个5，我们要找最右边的那个（下标为6，假设下标从 1 开始）。

核心逻辑：满足条件时，区间左边界向右移动，尽可能往右 “挤”。

场景 2：查找第一个 ≥ x 的元素

目标：在数组 [1, 2, 3, 5, 5, 5, 7, 8] 中，找到第一个 ≥ 5 的数的下标。

数组里有多个5，我们要找最左边的那个（下标为4，假设下标从 1 开始）。

核心逻辑：满足条件时，区间右边界向左移动，尽可能往左 “挤”。

二、模板 1：查找「最后一个 ≤ x」的元素（适合求 “上界”、“不大于 x 的最大值” 等问题）

三种实现方式对比

方式 1：开区间写法（推荐）

int find(int q){int l=0, r=n+1; // 左开右开区间 [l, r)while(l+1 < r){ // 当l和r相邻时结束int mid = l + r >> 1;if(a[mid] <= q) l = mid; // 满足条件，左边界右移else r = mid; // 不满足条件，右边界左移}return l;
}

✅ 优点：边界条件清晰，循环结束时l和r一定相邻，l就是答案。

⚠️ 注意：下标从 1 开始，所以初始化l=0，r=n+1。

方式 2：闭区间写法（向上取整）

int find(int q){int l=1, r=n; // 闭区间 [l, r]while(l < r){ // 当l == r时结束int mid = l + r + 1 >> 1; // 注意这里要+1，向上取整！if(a[mid] <= q) l = mid; else r = mid - 1; }return l;
}

✅ 优点：下标直接和数组对应，容易理解。

⚠️ 注意：必须使用 mid = l + r + 1 >> 1，否则会陷入死循环！

方式 3：记录答案写法（最通用）

int find(int q){int ans = 0;int l=1, r=n; // 闭区间 [l, r]while(l <= r){ // 当l > r时结束int mid = l + r >> 1;if(a[mid] <= q){ans = mid; // 记录当前满足条件的位置l = mid + 1; // 继续向右找更靠后的} else {r = mid - 1;}}return ans;
}

✅ 优点：逻辑最直白，不容易写错，适合新手。

⚠️ 注意：需要额外定义一个变量 ans 来保存答案。

三、模板 2：查找「第一个 ≥ x」的元素（适合求 “下界”、“不小于 x 的最小值”、lower_bound等问题）

三种实现方式对比

方式 1：开区间写法（推荐）

int find(int q){int l=0, r=n+1; // 左开右开区间 [l, r)while(l+1 < r){ // 当l和r相邻时结束int mid = l + r >> 1;if(a[mid] >= q) r = mid; // 满足条件，右边界左移else l = mid; // 不满足条件，左边界右移}return r;
}

✅ 优点：和模板 1 对称，逻辑统一，边界清晰。

⚠️ 注意：循环结束时 r 就是答案。

方式 2：闭区间写法（向下取整）

int find(int q){int l=1, r=n; // 闭区间 [l, r]while(l < r){ // 当l == r时结束int mid = l + r >> 1; // 直接向下取整即可if(a[mid] >= q) r = mid; else l = mid + 1; }return r;
}

✅ 优点：下标直接和数组对应，容易理解。

⚠️ 注意：这里 mid 不需要 + 1，直接 l + r >> 1 即可。

方式 3：记录答案写法（最通用）

int find(int q){int ans = 0;int l=1, r=n; // 闭区间 [l, r]while(l <= r){ // 当l > r时结束int mid = l + r >> 1;if(a[mid] >= q){ans = mid; // 记录当前满足条件的位置r = mid - 1; // 继续向左找更靠前的} else {l = mid + 1;}}return ans;
}

✅ 优点：逻辑最直白，不容易写错，适合新手。

⚠️ 注意：需要额外定义一个变量 ans 来保存答案。

四、核心区别总结表

场景	关键判断	区间移动	mid 计算	推荐模板
找最后一个 ≤ x	a[mid] <= x	l = mid	需向上取整（+1）	开区间 / 记录答案
找第一个 ≥ x	a[mid] >= x	r = mid	直接向下取整	开区间 / 记录答案

五、避坑指南（新手必看）

死循环问题

当使用 while(l < r) 写 “找最后一个” 的问题时，mid 必须向上取整（(l + r + 1) / 2），否则当 l = r - 1 时，mid 永远等于 l，导致死循环。

写 “找第一个” 的问题时，mid 直接向下取整即可，不会死循环。

边界初始化问题

• 开区间写法：l=0, r=n+1，这样可以处理数组中不存在满足条件元素的情况（返回0或n+1）。
• 闭区间写法：l=1, r=n，如果不存在满足条件的元素，需要额外判断返回值是否合法。

下标从 0 还是从 1 开始？

• 从 1 开始：更符合上面的模板写法，处理边界更方便。
• 从 0 开始：需要把 l 初始化为 -1，r 初始化为 n，逻辑是一样的。