Hello 算法：基于分治的递归二分查找——O(log n) 搜索的递归实现全解

Hello 算法：基于分治的递归二分查找——O(log n) 搜索的递归实现全解

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo

在《Hello 算法》的「分治算法」章节中，二分查找的分治实现是一个承上启下的核心案例：它把前文「查找」章节里基于迭代（递推）的二分查找，改写为一个可递归分解的子问题求解过程。读完本篇，你将掌握二分查找的分治策略三条件判断依据、递归函数dfs()的子问题定义f(i, j)、完整的 Python / Java / C / Go / Rust 多语言实现，以及不同语言版本中中点计算防溢出的源码级细节。

搜索算法的两大阵营：暴力与自适应

《Hello 算法》将搜索算法分为两大类：

• 暴力搜索：通过遍历数据结构实现，时间复杂度为 $O(n)$ 。
• 自适应搜索：利用特有的数据组织形式或先验信息（例如数组有序这一先验信息），时间复杂度可达到 $O(\log n)$ 甚至 $O(1)$ 。

一个关键论断是：时间复杂度为 $O(\log n)$ 的搜索算法通常是基于分治策略实现的，典型代表就是二分查找和树。

• 二分查找的每一步都将问题（在数组中搜索目标元素）分解为一个小问题（在数组的一半中搜索目标元素），这个过程一直持续到数组为空或找到目标元素为止。
• 树是分治思想的代表，在二叉搜索树、AVL 树、堆等数据结构中，各种操作的时间复杂度皆为 $O(\log n)$ 。

为什么是 $O(\log n)$ 而不是 $O(n)$？本质原因在于：暴力搜索每轮只能排除一个选项，而分治搜索每轮可以排除一半选项。经过 $k$ 轮排除后，候选规模从 $n$ 收缩到 $n / 2^k$，令其小于 1 可得 $k = O(\log n)$ 。

二分查找满足分治的三个判断条件

一个搜索问题是否适合用分治解决，可以对照三条判断依据逐一验证。以「在有序数组中查找目标元素」为例：

1. 问题可以分解：二分查找递归地将原问题（在数组中进行查找）分解为子问题（在数组的一半中进行查找），这是通过比较中间元素和目标元素来实现的。
2. 子问题是独立的：在二分查找中，每轮只处理一个子问题，它不受其他子问题的影响。
3. 子问题的解无须合并：二分查找旨在查找一个特定元素，因此不需要将子问题的解进行合并。当子问题得到解决时，原问题也会同时得到解决。

第三条与归并排序形成鲜明对比——归并排序的子问题解必须自底向上合并，而搜索类分治是「沿单一路径下钻」，没有合并阶段。这也是分治在搜索场景中实现特别简洁的原因。

下图展示了在数组中二分查找元素 $6$ 的分治过程（每层递归只保留一个子问题继续求解）：

问题定义与求解步骤

原题如下：

给定一个长度为 $n$ 的有序数组nums，其中所有元素都是唯一的，请查找元素target。

从分治角度，我们将搜索区间 $[i, j]$ 对应的子问题记为 $f(i, j)$ 。以原问题 $f(0, n-1)$ 为起始点，求解步骤为：

1. 计算搜索区间 $[i, j]$ 的中点 $m$，根据它排除一半搜索区间。
2. 递归求解规模减小一半的子问题，可能为 $f(i, m-1)$ 或 $f(m+1, j)$ 。
3. 循环第 1 步和第 2 步，直至找到target或区间为空时返回。

两个递归出口分别是：

• 命中出口：nums[m] == target，返回m；
• 失败出口：i > j（区间为空），代表无目标元素，返回-1。

递归实现：Python 完整源码

仓库中的 Python 实现见 binary_search_recur.py，声明一个递归函数dfs()来求解问题 $f(i, j)$ ：

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) """Driver Code""" if __name__ == "__main__": target = 6 nums = [1, 3, 6, 8, 12, 15, 23, 26, 31, 35] # 二分查找（双闭区间） index = binary_search(nums, target) print("目标元素 6 的索引 = ", index)

运行该文件，输出目标元素 6 的索引 = 2。注意这里使用的是双闭区间$[i, j]$ 约定：初始区间为 $[0, n-1]$，命中条件为nums[m] == target，两个分支分别收缩为 $[m+1, j]$ 与 $[i, m-1]$ 。这一约定与「查找」章节中迭代版本的三分支写法（<、>、==各走各的分支）完全一致，只是在控制结构上用递归替换了while循环。

跨语言实现：C / C++ / Java / Go / Rust 的同一套骨架

同一算法在仓库中提供了多语言实现，骨架完全一致（dfs+binarySearch入口），可直接对照阅读：

• Python：binary_search_recur.py
• Java：binary_search_recur.java
• C：binary_search_recur.c
• C++：binary_search_recur.cpp
• Go：binary_search_recur.go
• Rust：binary_search_recur.rs
• C# / Kotlin / Swift / TypeScript / Ruby / Dart / JavaScript 等：各语言chapter_divide_and_conquer目录下同名文件（如 binary_search_recur.kt、binary_search_recur.ts）

以 Java 版本为例（binary_search_recur.java）：

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

源码细节：中点计算的两种写法

对比各语言实现可以发现一个值得注意的差异——中点m的计算方式有两类：

Go 和 Rust 版本采用的是防溢出写法：先算差值(j - i)再折半（Go 进一步用右移一位表示除以 2），可避免i + j在索引极大时溢出；Python 整数无溢出问题，C/Java 等版本在索引为常规int范围时(i + j) / 2是安全的简化写法。从源码结构看，这是多语言教学实现中刻意保留的一种「同一算法、不同工程约束」的对照细节。

测试用例：命中与不命中两条路径

Go 版本的单元测试（binary_search_recur_test.go）覆盖了两类出口：

func TestBinarySearch(t *testing.T) { nums := []int{1, 3, 6, 8, 12, 15, 23, 26, 31, 35} target := 6 noTarget := 99 targetIndex := binarySearch(nums, target) fmt.Println("目标元素 6 的索引 = ", targetIndex) noTargetIndex := binarySearch(nums, noTarget) fmt.Println("不存在目标元素的索引 = ", noTargetIndex) }

• 查找6走命中出口，返回索引2；
• 查找不存在的99走失败出口（区间收缩至i > j），返回-1。

这两个断言恰好对应dfs()的两个递归出口，是最小的完整验证集。

递归版本的复杂度分析

• 时间复杂度 $O(\log n)$：每轮递归将区间长度减半，递归次数至多 $\lceil \log_2 n \rceil + 1$ 层，每层只执行常数时间的比较与中点计算，总时间复杂度为 $O(\log n)$ 。
• 空间复杂度 $O(\log n)$：从源码结构看，递归调用链的深度即最坏情况下的递归层数，每层在调用栈上保存i、j等常数个局部变量，因此栈空间为 $O(\log n)$ 。这与迭代版本 $O(1)$ 的额外空间不同——递归版用栈帧换来了更贴近「子问题定义」的表达形式。

与迭代版本的对应关系

「查找」章节中的迭代版二分查找（参见 docs/chapter_searching/binary_search.md）用一个while循环维护i、j两个指针；本节的递归版则把「当前搜索区间」直接编码为函数参数i、j，把「循环推进区间」变成「递归收缩区间」。两者的状态转移一一对应：

换言之，分治版并没有改变二分查找的算法本体，而是换一种「问题 → 子问题」的视角来组织代码，这正是 分治算法 一节所讲的「分而治之」在搜索问题上的最小示范：分（按中点划分区间）、治（递归求解半边），且由于子问题的解无须合并，「治」的结果直接就是原问题的答案。

【免费下载链接】hello-algo《Hello 算法》：动画图解、一键运行的数据结构与算法教程。支持简中、繁中、English、日本語，提供 Python, Java, C++, C, C#, JS, Go, Swift, Rust, Ruby, Kotlin, TS, Dart 等代码实现项目地址: https://gitcode.com/GitHub_Trending/he/hello-algo