当前进度第 1 个 / 总共 30 个算法轮播列表二分查找 → 快速排序 → 归并排序 → BFS → DFS → 动态规划-背包 → Dijkstra → KMP → 拓扑排序 → 并查集 → 线段树 → 堆排序 → 红黑树 → A*寻路 → Trie字典树 → Floyd-Warshall → Prim/Kruskal最小生成树 → 回溯法-N皇后 → 贪心-区间调度 → 哈希表与冲突解决 → LRU Cache → 滑动窗口 → 单调栈 → 树状数组 → Bellman-Ford → Rabin-Karp → 快速幂 → 欧几里得GCD → 筛法求素数 → 动态规划-LCS一、为什么从二分查找开始二分查找是算法世界的”瑞士军刀”——思路极简应用极广。它是理解”分治思想”和”对数复杂度”的起点也是面试中出现频率最高的基础算法之一。Google 曾在一次面试中让候选人实现二分查找结果 90% 的人写不对——不是因为难而是因为边界条件太容易踩坑。二、核心原理2.1 基本思想二分查找的前提条件数据必须有序。核心思路只有一句话每次取中间元素与目标值比较如果相等则找到如果目标更小则在左半部分继续查找如果目标更大则在右半部分继续查找。每一轮将搜索范围缩小一半。这就像翻字典你要找”猫”这个字翻开中间发现是”水”“猫”在”水”前面于是你只看前半本。再来一次翻前半本的中间……几次下来就找到了。配图 1二分查找原理图 — 有序数组 low/mid/high 三指针示意2.2 时间复杂度最优时间O(1)第一次就命中最坏时间O(log n)平均时间O(log n)空间复杂度迭代 O(1)递归 O(log n)为什么是 O(log n) 假设数组有 n 个元素每轮砍掉一半最多砍 k 轮直到剩 1 个n / 2^k 1 → k log₂n。对于 10 亿条数据二分查找最多只需要约 30 次比较。配图 2线性查找 vs 二分查找效率对比2.3 关键细节三个指针low搜索区间的左边界high搜索区间的右边界mid中间位置mid low (high - low) / 2⚠️ 为什么不用 mid (low high) / 2因为 low high 可能溢出当 low 和 high 都很大时它们的和可能超过 int 的最大值。用 low (high - low) / 2 可以避免这个问题。三、图解过程在数组 [2,5,8,12,16,23,38,56,72,91] 中查找 23配图 3二分查找三步过程可视化二分查找三步过程可视化第 1 轮 - 搜索范围索引 0 ~ 9全部 10 个元素 - mid 0 (9-0)/2 4arr[4] 16 - 23 16 → 目标在右半部分low mid 1 5第 2 轮 - 搜索范围索引 5 ~ 9剩 5 个元素23, 38, 56, 72, 91 - mid 5 (9-5)/2 7arr[7] 56 - 23 56 → 目标在左半部分high mid - 1 6第 3 轮 - 搜索范围索引 5 ~ 6剩 2 个元素23, 38 - mid 5 (6-5)/2 5arr[5] 23 - 23 23 → 命中返回索引 5四、完整代码实现4.1 Python 迭代实现from typing import List, Optionaldef binary_search(arr: List[int], target: int) Optional[int]:在有序数组中查找目标值的索引。Args:arr: 升序排列的整数数组target: 要查找的目标值Returns:目标值的索引未找到返回 Nonelow, high 0, len(arr) - 1while low high:mid low (high - low) // 2 # 防溢出写法if arr[mid] target:return midelif arr[mid] target:low mid 1else:high mid - 1return None # 未找到# 测试 if __name__ __main__:data [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]# 测试找到目标result binary_search(data, 23)print(f查找 23: 索引 {result}) # 输出: 索引 5# 测试目标不存在result binary_search(data, 10)print(f查找 10: 索引 {result}) # 输出: 索引 None# 测试查找第一个元素result binary_search(data, 2)print(f查找 2: 索引 {result}) # 输出: 索引 0# 测试查找最后一个元素result binary_search(data, 91)print(f查找 91: 索引 {result}) # 输出: 索引 9# 测试空数组result binary_search([], 5)print(f空数组查找 5: 索引 {result}) # 输出: 索引 None4.2 Python 递归实现def binary_search_recursive(arr: List[int], target: int,low: int 0, high: int None) Optional[int]:递归版二分查找if high is None:high len(arr) - 1# 递归终止条件if low high:return Nonemid low (high - low) // 2if arr[mid] target:return midelif arr[mid] target:return binary_search_recursive(arr, target, mid 1, high)else:return binary_search_recursive(arr, target, low, mid - 1)4.3 Java 实现public class BinarySearch {/*** 在有序数组中查找目标值的索引迭代版** param arr 升序排列的整数数组* param target 要查找的目标值* return 目标值的索引未找到返回 -1*/public static int binarySearch(int[] arr, int target) {int low 0;int high arr.length - 1;while (low high) {int mid low (high - low) / 2; // 防溢出if (arr[mid] target) {return mid;} else if (arr[mid] target) {low mid 1;} else {high mid - 1;}}return -1; // 未找到}/*** 递归版二分查找*/public static int binarySearchRecursive(int[] arr, int target,int low, int high) {if (low high) {return -1;}int mid low (high - low) / 2;if (arr[mid] target) {return mid;} else if (arr[mid] target) {return binarySearchRecursive(arr, target, mid 1, high);} else {return binarySearchRecursive(arr, target, low, mid - 1);}}// 测试 public static void main(String[] args) {int[] data {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};System.out.println(查找 23: 索引 binarySearch(data, 23)); // 5System.out.println(查找 10: 索引 binarySearch(data, 10)); // -1System.out.println(查找 2: 索引 binarySearch(data, 2)); // 0System.out.println(查找 91: 索引 binarySearch(data, 91)); // 9// 递归版System.out.println(递归查找 23: 索引 binarySearchRecursive(data, 23, 0, data.length - 1)); // 5}}五、进阶变体基础二分只是起点。实际面试和工程中常考的二分变体有以下几种5.1 查找第一个等于目标的位置def find_first(arr: List[int], target: int) int:low, high 0, len(arr) - 1result -1while low high:mid low (high - low) // 2if arr[mid] target:result mid # 记录当前位置high mid - 1 # 继续向左找elif arr[mid] target:low mid 1else:high mid - 1return result5.2 查找最后一个等于目标的位置def find_last(arr: List[int], target: int) int:low, high 0, len(arr) - 1result -1while low high:mid low (high - low) // 2if arr[mid] target:result mid # 记录当前位置low mid 1 # 继续向右找elif arr[mid] target:low mid 1else:high mid - 1return result5.3 查找第一个大于等于目标的位置下界def lower_bound(arr: List[int], target: int) int:low, high 0, len(arr)while low high:mid low (high - low) // 2if arr[mid] target:low mid 1else:high midreturn low六、常见踩坑点循环条件踩坑low high vs low high闭区间用 半开区间用 mid 计算踩坑(low high) / 2 可能溢出应使用 low (high - low) / 2边界更新踩坑low mid 或 high mid 可能导致死循环应明确使用 mid 1 或 mid - 1未排序数据踩坑对无序数组直接用二分会出错必须先排序或换其他查找方式返回值混淆踩坑返回索引 vs 返回值 vs 返回 -1 vs None需根据场景统一约定七、实际应用场景二分查找不仅仅是”在数组里找数”它的思想渗透在很多场景中数据库索引查找 — B树每一层内部就是二分Git bisect — 用二分法定位哪次 commit 引入了 bug数值计算 — 求平方根、求中位数本质都是二分答案搜索空间缩减 — 只要答案空间有序且可判定就能二分如”最小的能满足条件的值”标准库函数 — Python 的 bisect 模块、Java 的 Arrays.binarySearch()、C 的 std::lower_bound()八、一句话总结二分查找的精髓不在于”找”而在于”砍”——每一步都能确定性地扔掉一半不可能的区域。掌握它的关键只有一个搞清楚循环不变量loop invariant是什么。下期预告#2/30 快速排序Quick Sort—— 分治思想的经典之作本文属于「算法知识轮播」系列共 30 期按固定顺序逐一推送。