二分查找
最后更新
二分查找通过不断把搜索窗口减半，在**有序**数组中找到目标值。它把中间元素和目标值比较：相等就结束查找；否则就丢弃不可能包含目标值的那一半，窗口缩小到另一半。每次比较都会排除剩余元素的一半，所以它的复杂度是 O(log n)：在一百万个有序值中查找，最多只需要大约 20 次比较。
上面的动画显示了 lo、mid 和 hi 三个指针，并在每次比较后把被排除的一半变暗。有一个前提条件不容商量：数组必须已经有序。对于无序数据，你需要使用线性查找，或者先排序（参见归并排序）。同样的折半思想也是二叉搜索树的基础。
时间和空间复杂度
| 情况 | 复杂度 | 说明 |
|---|---|---|
| 最好情况 | O(1) | 第一次比较时中间元素就是目标值。 |
| 平均情况 | O(log n) | 每次比较都把剩余窗口减半。 |
| 最坏情况 | O(log n) | 窗口缩小到只剩一个元素，才确定找到或找不到。 |
| 空间 | O(1) | 迭代版本只保存 lo、hi 和 mid 三个下标。 |
分步说明
| 步骤 | 发生了什么 |
|---|---|
| 1 | 把 lo 设为有序数组的第一个下标，把 hi 设为最后一个下标。 |
| 2 | 计算中间下标：mid = (lo + hi) // 2。 |
| 3 | 如果 a[mid] 等于目标值，返回 mid（找到了）。 |
| 4 | 如果 a[mid] **小于**目标值，目标值只可能在右半部分：令 lo = mid + 1。 |
| 5 | 如果 a[mid] **大于**目标值，就在左半部分查找：令 hi = mid - 1。 |
| 6 | 只要 lo <= hi，就从第 2 步开始重复；如果窗口为空，说明目标值不在数组中。 |
示例演算
在 [1, 2, 3, 5, 7, 8, 9] 中查找 5：
| 轮次 | 窗口 (lo..hi) | mid | a[mid] | 操作 |
|---|---|---|---|---|
| 1 | [1, 2, 3, 5, 7, 8, 9] (0..6) | 3 | 5 | a[3] = 5：在下标 3 处找到目标值。 |
查找失败的过程
在同一个数组中查找 4，可以看到窗口是如何变空的：
| 轮次 | 窗口 (lo..hi) | mid | a[mid] | 操作 |
|---|---|---|---|---|
| 1 | 0..6 | 3 | 5 | 5 > 4：在左半部分查找，hi = 2。 |
| 2 | 0..2 | 1 | 2 | 2 < 4：在右半部分查找，lo = 2。 |
| 3 | 2..2 | 2 | 3 | 3 < 4，所以 lo 变为 3，窗口变空：没有找到。 |
什么时候使用二分查找
| 适合使用的情况 | 不适合使用的情况 |
|---|---|
| 数据已经有序（或者需要多次查找） | 数据无序且只查找一次（先排序要花 O(n log n)） |
| 集合支持快速随机访问（数组） | 只能顺序访问（链表） |
数据量很大（O(log n) 在大规模数据上优势明显） | 数据量很小（简单扫描一样快，而且更简单） |
Binary Search 代码
简洁、可运行的 Binary Search 实现，提供 Python, JavaScript, Java, C++, C, Pseudocode 版本。选择一种语言，复制代码，或在 Coddy 在线编辑器中直接打开。
Binary Search 的 Python 代码
Python
1def binary_search(a, target):2 lo, hi = 0, len(a) - 13 while lo <= hi:4 mid = (lo + hi) // 25 if a[mid] == target:6 return mid7 if a[mid] < target:8 lo = mid + 1 # search the right half9 else:10 hi = mid - 1 # search the left half11 return -112
13
14nums = [1, 2, 3, 5, 7, 8, 9] # must be sorted15print("Index of 5:", binary_search(nums, 5))16print("Index of 4:", binary_search(nums, 4))Binary Search 的 JavaScript 代码
JavaScript
1function binarySearch(a, target) {2 let lo = 0;3 let hi = a.length - 1;4 while (lo <= hi) {5 const mid = Math.floor((lo + hi) / 2);6 if (a[mid] === target) return mid;7 if (a[mid] < target) {8 lo = mid + 1; // search the right half9 } else {10 hi = mid - 1; // search the left half11 }12 }13 return -1;14}15
16const nums = [1, 2, 3, 5, 7, 8, 9]; // must be sorted17console.log("Index of 5:", binarySearch(nums, 5));18console.log("Index of 4:", binarySearch(nums, 4));Binary Search 的 Java 代码
Java
1public class Main {2 static int binarySearch(int[] a, int target) {3 int lo = 0;4 int hi = a.length - 1;5 while (lo <= hi) {6 int mid = (lo + hi) / 2;7 if (a[mid] == target) return mid;8 if (a[mid] < target) {9 lo = mid + 1; // search the right half10 } else {11 hi = mid - 1; // search the left half12 }13 }14 return -1;15 }16
17 public static void main(String[] args) {18 int[] nums = {1, 2, 3, 5, 7, 8, 9}; // must be sorted19 System.out.println("Index of 5: " + binarySearch(nums, 5));20 System.out.println("Index of 4: " + binarySearch(nums, 4));21 }22}Binary Search 的 C++ 代码
C++
1#include <iostream>2#include <vector>3
4int binarySearch(const std::vector<int>& a, int target) {5 int lo = 0;6 int hi = static_cast<int>(a.size()) - 1;7 while (lo <= hi) {8 int mid = lo + (hi - lo) / 2;9 if (a[mid] == target) return mid;10 if (a[mid] < target) {11 lo = mid + 1; // search the right half12 } else {13 hi = mid - 1; // search the left half14 }15 }16 return -1;17}18
19int main() {20 std::vector<int> nums = {1, 2, 3, 5, 7, 8, 9}; // must be sorted21 std::cout << "Index of 5: " << binarySearch(nums, 5) << "\n";22 std::cout << "Index of 4: " << binarySearch(nums, 4) << "\n";23 return 0;24}Binary Search 的 C 代码
C
1#include <stdio.h>2
3int binary_search(const int a[], int n, int target) {4 int lo = 0;5 int hi = n - 1;6 while (lo <= hi) {7 int mid = lo + (hi - lo) / 2;8 if (a[mid] == target) return mid;9 if (a[mid] < target) {10 lo = mid + 1; /* search the right half */11 } else {12 hi = mid - 1; /* search the left half */13 }14 }15 return -1;16}17
18int main(void) {19 int nums[] = {1, 2, 3, 5, 7, 8, 9}; /* must be sorted */20 int n = sizeof(nums) / sizeof(nums[0]);21 printf("Index of 5: %d\n", binary_search(nums, n, 5));22 printf("Index of 4: %d\n", binary_search(nums, n, 4));23 return 0;24}Binary Search 的 Pseudocode 代码
Pseudocode
1DECLARE nums : ARRAY[1:7] OF INTEGER2DECLARE n : INTEGER3n ← 74// The array must be sorted for binary search5nums[1] ← 16nums[2] ← 27nums[3] ← 38nums[4] ← 59nums[5] ← 710nums[6] ← 811nums[7] ← 912
13FUNCTION binarySearch(target : INTEGER) RETURNS INTEGER14 DECLARE lo : INTEGER15 DECLARE hi : INTEGER16 DECLARE mid : INTEGER17 lo ← 118 hi ← n19 WHILE lo <= hi DO20 mid ← (lo + hi) DIV 221 IF nums[mid] = target THEN22 RETURN mid23 ENDIF24 IF nums[mid] < target THEN25 // Target is larger, search the right half26 lo ← mid + 127 ELSE28 // Target is smaller, search the left half29 hi ← mid - 130 ENDIF31 ENDWHILE32 RETURN -133ENDFUNCTION34
35OUTPUT "Index of 5 is ", binarySearch(5)36OUTPUT "Index of 4 is ", binarySearch(4)二分查找常见问题
二分查找的时间复杂度是多少？
平均和最坏情况都是
O(log n)，因为每次比较都会把剩余的搜索窗口减半；最好情况是 O(1)，即第一个中间元素就是目标值。迭代版本只占用 O(1) 的额外空间。为什么二分查找要求数组有序？
折半这一步依赖顺序：只有当中间元素左边的值都更小、右边的值都更大时，把目标值和中间元素比较，才能知道该丢弃哪一半。在无序数据上这个推断不成立，所以应改用线性查找，或者先排序。
二分查找和线性查找有什么区别？
线性查找逐个扫描元素（
O(n)），适用于任何数组；二分查找把有序数组的搜索窗口不断减半（O(log n)），但要求输入有序。元素只有几个时差别可以忽略，数据量大时二分查找完胜。二分查找需要多少次比较？
最多大约
log2(n) + 1 次：10 次比较可以覆盖 1,000 个元素，20 次比较可以覆盖 1,000,000 个。正是这种对数级增长，让它成为有序数据上默认的查找方法。二分查找中经典的溢出 bug 是什么？
当
lo + hi 超过类型的最大值时，用 (lo + hi) / 2 计算中间下标会让定长整数溢出。安全的写法是 mid = lo + (hi - lo) / 2。在 Python 中这无关紧要（整数精度不受限制），但在 Java、C、C++ 中这是一个真实存在、而且很有名的 bug。二分查找和二叉搜索树是一回事吗？
它们共享折半的思想，但结构不同：二分查找是作用在有序数组上的算法，而二叉搜索树是一种链式数据结构，它让键保持有序，查找时在每个节点处向左或向右下行。
相关资源
更多可视化
