《Hello 算法》分治搜索策略剖析：基于递归的二分查找 binary_search_recur 详解

导读

本文以《Hello 算法》日文版 分治搜索策略章节 为核心，系统讲解时间复杂度为 O(log n) 的搜索算法为何普遍建立在分治（divide and conquer）之上，并从递归视角推导出二分查找的完整实现路径。读者学完后，将掌握暴力搜索与自适应搜索的分野、二分查找满足的三大分治特征、搜索区间子问题 f(i, j) 的形式化建模方法，以及 binary_search_recur 在 Python/C/C++ 等 14 种语言中的真实源码形态与运行验证方式。

一、搜索算法的两大分类：暴力搜索与自适应搜索

《Hello 算法》在引入分治搜索策略时，首先给出了搜索算法的两大分类框架：

• 暴力搜索（brute-force search）：通过遍历数据结构实现，通常需要逐个检查候选元素，时间复杂度为 O(n)。典型例子是对无序数组做线性扫描，每轮仅能排除一个候选。
• 自适应搜索（adaptive search）：利用数据特有的组织形式或先验信息（例如元素有序、树形层级关系），时间复杂度可达到 O(log n) 甚至 O(1)。

一个容易被忽略的观察是：时间复杂度的数量级往往取决于算法的“组织方式”。顺序存储、逐个比较只能带来 O(n)；而一旦借助有序性、层级结构等先验信息，搜索成本就能以对数级甚至常数级下降。

二、O(log n) 的搜索算法通常建立在分治策略之上

本节的核心理点是一句话：时间复杂度为 O(log n) 的搜索算法，通常是基于分治策略实现的。文中给出了两类证据：

1. 二分查找：每一步都将“在数组中搜索目标元素”这一问题，分解为“在数组的一半中搜索目标元素”这一更小问题；该过程持续到数组为空或找到目标元素为止。也就是说，一次 O(log n) 的搜索背后，是一棵深度为 O(log n) 的递归分解树。
2. 树形数据结构：树本身就是“递归分割”思想的可视化载体。二分搜索树、AVL 树、堆等数据结构的各类操作，时间复杂度均为 O(log n)。仓库中对应章节可继续深入：二分搜索树、AVL 树、堆。

值得注意的是，二分查找的分治特性与经典的归并排序同源——归并排序“分而治之”的完整推导（分解→求解→合并）记录在本章总论 divide_and_conquer.md 中，其中给出了分治适用问题的通用判断标准，而二分查找正是该标准的“特例应用”。

三、二分查找满足分治的三大特征

判断一个问题是否适合分治，通常看三条标准（详见 分割統治法章节）。二分查找恰好三条全部满足：

分治特征	二分查找中的体现
问题可以分解	原问题（在整个数组中查找）被递归分解为子问题（在数组的一半中查找），这是通过比较中间元素 nums[m] 与目标 target 的大小实现的
子问题是独立的	每轮只处理一个子问题，且该子问题的求解不受其他子问题影响——target 一旦被确定落在左半区或右半区，另一侧就被彻底丢弃，不存在跨子问题的依赖
子问题的解无须合并	二分查找的目标是找到某个特定元素，找到即结束；子问题得到解决时，原问题同时得到解决，不需要像归并排序那样自底向上“合并”子结果

第三点（无须合并）是二分查找区别于大多数分治算法的关键：例如归并排序必须把两个有序子数组 merge 回原数组，而二分查找沿单一路径下探、命中即返回，天然省去“治”的合并开销。

四、分治为何能提升搜索效率：每轮排除一半候选

分治能够提升搜索效率，其本质原因被书中概括为一句对比：

暴力搜索每轮只能排除一个选项，而分治搜索每轮可以排除一半选项。

从复杂度角度理解：暴力线性扫描的最坏情况需要比较全部 n 个元素；而基于有序性 + 中间值比较的分治策略，每轮把候选区间折半，经过 O(log n) 轮后区间即收敛为空或命中目标。这就是自适应搜索从 O(n) 跃迁到 O(log n) 的根本机制。同样的机制也解释了树形结构操作的 O(log n) 成本——树高即递归分解的层数。

五、问题建模：将搜索区间形式化为子问题 f(i, j)

为了用递归实现二分查找，需要把“区间”这一直觉概念形式化为可递归调用的子问题。

假设给定一个长度为 n 的升序数组 nums，其中所有元素唯一，需要查找元素 target。将搜索区间 [i, j] 对应的子问题记作 f(i, j)，其中 i、j 分别指向区间的首、尾元素下标（闭区间，包含边界）。原问题即为 f(0, n-1)。

递归求解步骤如下：

1. 计算搜索区间 [i, j] 的中点下标 m，依据 nums[m] 与 target 的关系排除一半搜索区间；
2. 对规模缩小一半的子问题递归求解，候选子问题为 f(i, m-1)（目标在左半）或 f(m+1, j)（目标在右半）；
3. 重复步骤 1 与 2，直到找到 target 或区间为空时返回。

以在数组 [1, 3, 6, 8, 12, 15, 23, 26, 31, 35] 中查找元素 6 为例，图中演示了完整的递归下探过程：初始调用 f(0, 9) 取中点 m=4（值 12），因 6 < 12 递归左半区间 f(0, 3)；随后取中点 m=1（值 3），因 6 > 3 递归右半区间 f(2, 3)；最后取中点 m=2 命中 6，返回索引 2。

六、源码解读：以递归函数 dfs() 求解 f(i, j)

在仓库中，该章节代码实现文件名统一为 binary_search_recur，覆盖仓库支持的全部语言。以下以 Python 版本为解剖对象（完整源码见 binary_search_recur.py）：

def dfs(nums: list[int], target: int, i: int, j: int) -> int:
    """二分查找：问题 f(i, j)"""
    # 若区间为空，代表无目标元素，则返回 -1
    if i > j:
        return -1
    # 计算中点索引 m
    m = (i + j) // 2
    if nums[m] < target:
        # 递归子问题 f(m+1, j)
        return dfs(nums, target, m + 1, j)
    elif nums[m] > target:
        # 递归子问题 f(i, m-1)
        return dfs(nums, target, i, m - 1)
    else:
        # 找到目标元素，返回其索引
        return m


def binary_search(nums: list[int], target: int) -> int:
    """二分查找"""
    n = len(nums)
    # 求解问题 f(0, n-1)
    return dfs(nums, target, 0, n - 1)

代码与前面章节的英文标注一一对应，有四个值得展开的细节：

• 递归基（base case）：if i > j: return -1。当区间为空时说明数组不包含目标元素，返回 -1 表示“未找到”。这个 -1 会沿递归链逐层向上返回，直至最初的调用方。
• 中点计算：m = (i + j) // 2。Python 中整数无位数上限，此处直接用整除即可；而在 C/C++ 等定长整型语言中，i + j 存在大数越界的隐患，可改为 i + (j - i) / 2 的形式（该边界细节在 二分查找总览章节 中有专门讨论）。
• 三路分支：nums[m] < target 递归右半 f(m+1, j)；nums[m] > target 递归左半 f(i, m-1)；相等则直接返回命中下标 m。区间边界之所以是 m±1，是因为中点 m 已被比较过，无须纳入下一轮搜索。
• 入口封装：对外函数 binary_search 只负责把“整个数组”翻译成原问题 f(0, n-1)，真正的分治逻辑全部收敛在 dfs 内部，接口语义清晰。

七、多语言实现对照与运行验证

同一份逻辑在仓库中实现了 14 种语言。下面列出核心语言的入口文件，代码结构（dfs + binarySearch/binary_search 入口）完全一致，仅语法与中点写法略有差异：

语言	源码路径
Python	codes/python/chapter_divide_and_conquer/binary_search_recur.py
C	codes/c/chapter_divide_and_conquer/binary_search_recur.c
C++	codes/cpp/chapter_divide_and_conquer/binary_search_recur.cpp
Java	codes/java/chapter_divide_and_conquer/binary_search_recur.java
Go	codes/go/chapter_divide_and_conquer/binary_search_recur.go
JavaScript / TypeScript	codes/javascript/chapter_divide_and_conquer/binary_search_recur.js
Rust	codes/rust/chapter_divide_and_conquer/binary_search_recur.rs
Swift / Ruby / Kotlin / C# / Dart / Zig	见 codes 下对应 chapter_divide_and_conquer/binary_search_recur.*

运行与结果验证：各语言驱动代码均使用同一组测试数据——升序数组 nums = [1, 3, 6, 8, 12, 15, 23, 26, 31, 35]、目标值 target = 6，预期输出“目标元素 6 的索引 = 2”。例如 Python 版本可直接运行：

python3 codes/python/chapter_divide_and_conquer/binary_search_recur.py

C 版本则依赖 utils/common.h，已纳入 CMake 构建体系，其可执行目标在 chapter_divide_and_conquer/CMakeLists.txt 中以 add_executable(binary_search_recur ...) 声明，可按仓库文档介绍的方式构建运行。此外仓库还提供了 PythonTutor 逐帧可视化脚本（见 pythontutor 版 binary_search_recur），可直观观察递归调用栈的压栈与回溯过程。

八、递归版与迭代版二分查找的对比

章节开头指出，此前讨论的二分查找是基于**递推（迭代）实现的，而本节换用分治（递归）**视角重写。仓库中两版实现并存，可对照研读：

• 迭代版：codes/python/chapter_searching/binary_search.py 中的 binary_search，通过 while i <= j 循环与指针移动 i = m + 1 / j = m - 1 收缩区间，并用 return -1 处理未命中；
• 递归版：本文剖析的 binary_search_recur，把同样的区间收缩动作改写为对 f(i, m-1) 或 f(m+1, j) 的自我调用。

二者在数学上等价：递归版每次调用都把区间减半，故递归深度为 O(log n)。结合代码结构与经典算法分析可以推断：递归版时间开销同为 O(log n)，但因递归调用链需要占用调用栈空间，空间开销为 O(log n)；迭代版仅用常数个指针变量，空间开销为 O(1)（迭代版的复杂度结论在 binary_search.md 中有明确标注）。这也是工程实践中更偏爱迭代版二分查找的原因之一——而在教学与思维建模层面，递归版反而更直白地暴露了“每轮排除一半候选”的分治本质。

九、小结：从二分查找看分治思想的普适性

本章通过把二分查找“翻译”为递归形式，揭示了 O(log n) 搜索背后的统一思维模型：把一个大规模查找问题分解为可独立求解、且无须合并结果的子问题，沿单一路径逐层缩小搜索空间。

这一思想在《Hello 算法》中贯穿始终：本分治章节内还有重建二叉树、汉诺塔问题等递归应用；而更广义地，凡涉及“树高即代价”的数据结构操作（二分搜索树、AVL 树、堆），其效率来源都可回溯到“每轮排除一半”这一分治红利。理解 f(i, j) 这样的子问题建模方式，是读懂后续所有递归算法的第一块基石。