二分拆分思想

一句话算法

二分拆分就是每次把一个区间分成左右两半，问题规模不断减半，直到不能再分。

问题模型

很多算法都依赖同一个基础动作：

[l, r] -> [l, mid] 和 [mid+1, r]
mid = (l + r) / 2

这个动作本身不等于二分查找，但它是二分查找、线段树、归并排序、分治递归的共同基础。

核心直觉

如果一个区间长度为 n，每次都近似分成两半，那么最多分 $O(\log n)$ 层就会到达长度为 1 的区间。

例如：

[1, 8]
-> [1, 4] [5, 8]
-> [1, 2] [3, 4] [5, 6] [7, 8]
-> [1] [2] [3] [4] [5] [6] [7] [8]

这就是很多算法能得到对数层数的原因。

正确的区间拆分

闭区间 [l,r] 常用拆法是：

        
1
2
3

        int mid = (l + r) >> 1;
left = [l, mid];
right = [mid + 1, r];
    

这个拆法有两个关键性质：

1. 左右区间不重叠。
2. 左右区间合起来正好等于原区间。
3. 当 l < r 时，两个新区间都比原区间短。

第三点保证递归会停止。

常见错误

不要在闭区间里写成：

[l, mid] 和 [mid, r]

当区间长度为 2 时，例如 [1,2]：

mid = 1
[mid, r] = [1,2]

右区间没有变短，会导致递归无法结束。

算法证明

设当前区间长度为：

当 l < r 时，mid = floor((l+r)/2)。

左区间长度为：

右区间长度为：

二者都小于 len，因此递归规模严格减小，最终会到达 l == r。

每一层的区间互不重叠，且合并起来仍是原区间，所以不会漏掉元素，也不会重复覆盖元素。

复杂度分析

如果每层只进入一个子区间，例如二分查找：

• 层数：$O(\log n)$。
• 总复杂度：$O(\log n)$。

如果每层进入两个子区间，例如建线段树或归并排序：

• 层数：$O(\log n)$。
• 每层总元素量为 $O(n)$。
• 总复杂度通常为 $O(n\log n)$ 或建树的 $O(n)$，取决于每个节点做多少工作。

应用分类详解

二分拆分不是单独的算法，而是一种结构性思想。看到“区间不断折半”时，就应该想到它。

一、二分查找

典型模式： 只需要保留左右两半中的一半。

识别信号： 有单调性，答案在一段连续区间内。

核心建模： 每次用 mid 判断答案在哪一侧。

二、线段树

典型模式： 需要维护每个区间的信息。

识别信号： 有区间查询和修改。

核心建模： 每个节点维护一个二分拆出来的区间。

三、分治算法

典型模式： 把大问题拆成两个规模接近的小问题。

识别信号： 出现“先处理左半，再处理右半，最后合并”。

核心建模： 区间递归拆分，回溯时合并答案。

经典例题

1. 二分查找

在有序数组中查找边界，体现“只保留一半”的用法。

2. 线段树建树

每个节点使用 [l,mid] 和 [mid+1,r] 拆分区间。

3. 归并排序

递归排序左右两半，再用线性时间合并。