Quartz 4

二分查找

16 min read

二分查找虽然思想简单（“折半查找”），但在实际编码中，边界处理非常容易出错。因此，社区中发展出了几种主流的「二分模板」，它们在区间定义、循环条件、指针更新方式等方面有所不同。下面系统梳理三种最常用、最清晰的二分模板及其区别：

1 ✅ 模板一：闭区间模板（left ≤ right）

1.1 特点：

  • 搜索区间：[left, right]（两端都包含）
  • 循环条件：while (left <= right)
  • 每次排除 mid 后，更新为 mid ± 1

1.2 代码示例（找目标值）：

int left = 0, right = n - 1;
while (left <= right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] == target) return mid;
    else if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
}
return -1;

1.3 适用场景：

  • 精确查找某个值（存在性判断）
  • 需要明确返回“找到”或“未找到”

1.4 ⚠️ 注意：

  • 必须用 mid ± 1，否则可能死循环
  • 最终 left > right，无有效区间

2 ✅ 模板二：左闭右开模板（left < right）

2.1 特点：

  • 搜索区间：[left, right)（左包含，右不包含）
  • 循环条件：while (left < right)
  • 更新时：right = mid 或 left = mid + 1

2.2 代码示例（找第一个 ≥ target 的位置）：

int left = 0, right = n; // 注意 right = n
while (left < right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] >= target) {
        right = mid;
    } else {
        left = mid + 1;
    }
}
return left; // 插入位置 or 第一个 ≥ target 的索引

2.3 适用场景：

  • 查找边界（如第一个 ≥ x 的位置、最小值位置等）
  • LeetCode 中很多“旋转数组”“山脉数组”问题适用

2.4 优势：

  • 不容易死循环（因为区间严格缩小）
  • 最终 left == right，指向答案

3 ✅ 模板三：开区间模板（left + 1 < right）

3.1 特点：

  • 搜索区间：(left, right)（两端都不包含）
  • 初始设 left = -1, right = n
  • 循环条件：while (left + 1 < right)
  • 更新：left = mid 或 right = mid

3.2 代码示例（找旋转数组最小值）：

int left = -1, right = n; // 开区间 (-1, n)
while (left + 1 < right) {
    int mid = (left + right) >>> 1;
	    if (nums[mid] < nums[n - 1]) {
        right = mid;   // 保留 mid
    } else {
        left = mid;    // 排除 mid
    }
}
return nums[right]; // right 是第一个满足条件的位置

3.3 适用场景：

  • 所有需要找“分界点”的问题（如峰值、最小值、第一个满足条件的元素）
  • 逻辑最清晰：left 永远在“不满足区”，right 永远在“满足区”

3.4 优势：

  • 无需纠结 mid ± 1
  • 边界天然安全（-1 和 n 是哨兵）
  • 适合“染色法”思维：左边染红，右边染蓝，找红蓝分界

4 模版优势

为什么会有不同的模板，以及为什么某些场景下推荐特定模板。

4.1 核心原因：边界处理的清晰性和一致性

假设我们用双闭区间找第一个 ≥ target 的位置：

// 双闭区间 [-1, n-1] 或 [0, n-1]？
int left = 0, right = n - 1;
while (left <= right) {
    int mid = (left + right) / 2;
    if (nums[mid] >= target) {
        // 找到一个候选，但要继续找更左边的
        right = mid - 1;  // 这里排除 mid
    } else {
        left = mid + 1;
    }
}
// 最终答案是 left 还是 right？边界情况如何处理？

问题出现了：

  1. 初始边界难确定：如果数组所有元素都 < target，答案应该是 n，但双闭区间 [0, n-1] 无法表示 n
  2. 返回值困惑：循环结束后，left 和 right 的含义不直观
  3. 边界情况复杂：需要额外处理数组为空、全小于/大于等情况

4.2 左闭右开模板的优势

// 左闭右开 [0, n)
int left = 0, right = n;
while (left < right) {
    int mid = left + (right - left) / 2;
    if (nums[mid] >= target) {
        right = mid;    // mid 可能是答案，保留
    } else {
        left = mid + 1; // mid 不可能是答案，排除
    }
}
return left; // left 就是第一个 >= target 的位置

优势明显：

  1. 搜索空间完整：[0, n) 能表示所有可能答案（0 到 n）
  2. 返回值直观：直接返回 left
  3. 边界统一：无论什么情况，逻辑一致

4.3 具体对比示例

假设数组 nums = [1,3,5,7]，找第一个 ≥ 6 的位置（答案应该是 3）

4.3.1 双闭区间实现（复杂）

int left = 0, right = 3; // [0, 3]
while (left <= right) {
    int mid = (left + right) / 2;
    if (nums[mid] >= 6) {
        right = mid - 1;
    } else {
        left = mid + 1;
    }
}
// 循环结束：left = 3, right = 2
// 需要验证 left 是否越界，然后返回 left
if (left < n && nums[left] >= target) return left;
else return -1; // 或其他处理

4.3.2 左闭右开实现（简洁）

int left = 0, right = 4; // [0, 4)
while (left < right) {
    int mid = (left + right) / 2;
    if (nums[mid] >= 6) {
        right = mid;
    } else {
        left = mid + 1;
    }
}
return left; // 直接返回 3

4.4 关键洞察

模板的选择本质上是在选择”不变量”（loop invariant）：

  • 左闭右开：[left, right) 始终包含所有可能的答案
  • 双闭区间：[left, right] 包含待搜索的元素，但答案可能在区间外

当你需要返回插入位置或边界位置时，答案可能在原数组范围之外（如位置 n），这时候左闭右开的 [0, n) 就比双闭区间的 [0, n-1] 更自然。

4.5 总结

你可以用双闭区间实现任何二分查找，但：

  1. 代码更复杂：需要更多边界检查
  2. 容易出错：返回值的确定容易混淆
  3. 不够通用：难以处理答案在数组外的情况

而专门的模板通过精心设计的区间定义，让：

  • 搜索空间自然包含所有可能答案
  • 循环不变量清晰
  • 返回值直接就是答案

这就是为什么推荐在不同场景使用不同模板——不是不能用其他方式，而是特定模板能让代码更简洁、更不容易出错。

5 🆚 三种模板对比总结

  • 终止状态就是区间内为空值，例如对于[left, right]，终止状态为left > right，此时区间内恰好没有满足的整数；对于开区间 (left, right)，当left + 1 == right时，区间内恰好没有满足的整数
  • 更新方式则需要与循环内的判断条件相结合，例如在左闭右开区间内，当nums[mid] < target时，可知[left,mid]内均已排除，继续搜索[mid+1,right)区间，而如果nums[mid] >= target，则继续搜索[left,mid)，这里对于mid这个临界点都是排除了的，区别就在于搜索区间为开区间，所以更新方式有区别。与之对比的就是搜索区间为闭区间时，更新方式是对称的mid ± 1
特性闭区间 [left, right]左闭右开 [left, right)开区间 (left, right)
初始值left=0, right=n-1left=0, right=nleft=-1, right=n
循环条件left <= rightleft < rightleft + 1 < right
更新方式mid ± 1left = mid+1, right = midleft = mid, right = mid
终止状态left > rightleft == rightleft + 1 == right
易错点容易忘记 ±1 导致死循环需注意 right 初始为 n需理解“开区间”含义
适用问题精确查找边界查找（lower_bound）分界点问题（染色法）

6 实例

Warning

注意模版间的区别，一个区间是，一个是

6.1 查找给定数

static int binarySearch(int[] arr, int target) {
	int mid;
	int left = 0, right = arr.length - 1;
	while (left <= right) {
		mid = left + (right - left) / 2;
		if (arr[mid] == target) {
			return mid;
		} else if (arr[mid] > target) {
			right = mid - 1;
		} else {
			left = mid + 1;
		}
	}
	return -1;
}

6.2 第一个大于等于x的元素的位置(lower_bound)

Note

由于当left = right时 while循环停止,因此最后的返回值既可以是left,也可以是right

static int lower_bound(int[] arr, int target) {
	int mid;
	int left = 0,right = arr.length; // 注意：right 是数组长度，不是 length-1
	while (left < right) {
		mid = left + (right - left) / 2;  // 防止整数溢出的安全写法
		if (arr[mid] >= target) {
			right = mid;  // 目标可能在左半部分（包括mid）
		} else {
			left = mid + 1; // 目标一定在右半部分
		}
	}
	return left;  // 最终 left == right，返回任意一个都可以
}

  1. 搜索区间：[left, right)

    • right 初始化为 arr.length 而不是 arr.length - 1
    • 这样设计可以处理目标值大于所有元素的情况

  2. 边界处理：

    • 如果所有元素都小于 target，返回 arr.length
    • 如果所有元素都大于等于 target，返回 0

  3. 循环终止条件：left < right

    • 当 left == right 时循环结束
    • 此时 left 就是第一个 ≥ target 的位置

6.2.1 举例说明

假设数组 arr = [1, 2, 2, 3, 4, 4, 5]

target返回值说明
00第一个 ≥0 的位置是索引 0
21第一个 ≥2 的位置是索引 1
44第一个 ≥4 的位置是索引 4
67所有元素都 <6，返回数组长度

6.2.2 应用场景

  • 在有序数组中插入元素时确定插入位置
  • 查找第一个满足条件的元素
  • 实现其他二分查找变种的基础

这个算法的时间复杂度是 O(log n)，空间复杂度是 O(1)。

6.3 第一个大于x的元素的位置(upper_bound)

Tip

lower_bound(nums,target+1)等价于upper_bound(nums,target)

static int upper_bound(int[] arr, int target) {
	int mid;
	int left = 0, right = arr.length;
	while (left < right) {
		mid = left + (right - left) / 2;
		if (arr[mid] > target) {
			right = mid;
		} else {
			left = mid + 1;
		}
	}
	return left;
}

7 技巧

7.1 问题转换

在二分查找中，寻找满足特定比较条件（如 ≥、>、≤、<）的第一个或最后一个元素位置，是常见的问题。虽然表面上看这些条件不同，但它们都可以统一转化为“查找第一个大于等于某个值的位置”这一基本问题。这种统一思想有助于简化代码逻辑、避免重复实现，并加深对二分查找本质的理解。

其中：lower_bound（第一个 ≥ x），upper_bound（第一个 > x）

目标转化方式依赖函数
第一个 ≥ x直接使用lower_bound(x)
第一个 > xlower_bound(x + 1)（整数）
或实现 upper_bound		upper_bound(x)
最后一个 ≤ xupper_bound(x) - 1upper_bound
最后一个 < xlower_bound(x) - 1lower_bound

注意：upper_bound 本身也可以看作是“第一个 ≥ x 的变体”，只是判断条件变为 <= x。

实际上，upper_bound(x) = lower_bound(x’)，其中 x’ 是 x 的“上界”，但在通用类型中我们无法构造 x’，所以通常将 upper_bound 实现为独立但结构相同的二分模板。

7.2 溢出

// mid = (left+right)/2
// 方法1：避免溢出的加法
int mid = left + (right - left) / 2;
 
// 方法2：使用无符号右移
int mid = (left + right) >>> 1;

无符号右移

即使 left + right 溢出变成负数，其二进制表示仍然包含了正确的数值信息:

  • 无符号右移会将这个”错误”的负数当作无符号数来处理
  • 结果恰好等于 (left + right) / 2 的正确值 原因：
  • 整数溢出在二进制层面是模运算（mod 2^32）
  • (left + right) >>> 1 实际上计算的是 (left + right) mod 2^32 / 2
  • 由于我们只关心结果的低31位（正数范围），这个计算恰好给出了正确的中点值

7.3 上下取整转换公式

当 为非负整数， 为正整数时，有恒等式

参见上下取整转换公式

8 相关内容

二分查找 红蓝染色法【基础算法精讲 04】_哔哩哔哩_bilibili

Graph View

Backlinks