基本内容

介绍

「二分查找 binary search」是一种基于分治策略的高效搜索算法。它利用数据的有序性，每轮减少一半搜索范围，直至找到目标元素或搜索区间为空为止。

Q&A

1
2
Q:给定一个长度为 𝑛 的数组 nums ，元素按从小到大的顺序排列，数组不包含重复元素。请查找
并返回元素 target 在该数组中的索引。若数组不包含该元素，则返回−1。

BAvMXOSKbrXnYZww-e25c3d66-77f9-cdd3-7aa3-5aedf3c746d1|763
BAvMXOSKbrXnYZww-8e681b76-cead-bb24-50f1-d204f1fdcf48|944
BAvMXOSKbrXnYZww-f68255eb-f38d-ec41-1d65-50decfb59135|977

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/* 二分查找（双闭区间）(推荐) */
int binarySearch(vector<int> &nums, int target) {
	// 初始化双闭区间 [0, n-1] ，即 i, j 分别指向数组首元素、尾元素
	int i = 0, j = nums.size() - 1;
	// 循环，当搜索区间为空时跳出（当 i > j 时为空）
	while (i <= j) {
		int m = i + (j - i) / 2; // 计算中点索引 m
		if (nums[m] < target)// 此情况说明 target 在区间 [m+1, j] 中
			i = m + 1;
		else if (nums[m] > target) // 此情况说明 target 在区间 [i, m-1] 中
			j = m - 1;
		else // 找到目标元素，返回其索引
			return m;
	}
	// 未找到目标元素，返回 -1
	return -1;
}

/* 二分查找（左闭右开） */
int binarySearchLCRO(vector<int> &nums, int target) {
	// 初始化左闭右开 [0, n) ，即 i, j 分别指向数组首元素、尾元素 +1
	int i = 0, j = nums.size();
	// 循环，当搜索区间为空时跳出（当 i = j 时为空）
	while (i < j) {
		int m = i + (j - i) / 2; // 计算中点索引 m
		if (nums[m] < target)
			// 此情况说明 target 在区间 [m+1, j) 中
			i = m + 1;
		else if (nums[m] > target) // 此情况说明 target 在区间 [i, m) 中
			j = m;
		else // 找到目标元素，返回其索引
			return m;
	}
	// 未找到目标元素，返回 -1
	return -1;
}

BAvMXOSKbrXnYZww-1e86e6b5-8af6-f9fb-b22b-9f3145b8204d|744

优点与局限性

优点

  • 二分查找的时间效率高。在大数据量下，对数阶的时间复杂度具有显著优势。例如，当数据大小𝑛 = 220时，线性查找需要 220 = 1048576 轮循环，而二分查找仅需 log2 220 = 20 轮循环。
  • 二分查找无须额外空间。相较于需要借助额外空间的搜索算法（例如哈希查找），二分查找更加节省空间。

局限性

  • 二分查找仅适用于有序数据。若输入数据无序，为了使用二分查找而专门进行排序，得不偿失。因为排序算法的时间复杂度通常为 𝑂(𝑛 log 𝑛) ，比线性查找和二分查找都更高。对于频繁插入元素的场景，为保持数组有序性，需要将元素插入到特定位置，时间复杂度为 𝑂(𝑛) ，也是非常昂贵的。
  • 二分查找仅适用于数组。二分查找需要跳跃式（非连续地）访问元素，而在链表中执行跳跃式访问的效率较低，因此不适合应用在链表或基于链表实现的数据结构。
  • 小数据量下，线性查找性能更佳。在线性查找中，每轮只需要 1 次判断操作；而在二分查找中，需要 1次加法、1 次除法、1 ~ 3 次判断操作、1 次加法（减法），共 4 ~ 6 个单元操作；因此，当数据量 𝑛 较小时，线性查找反而比二分查找更快。

二分查找插入点

二分查找不仅可用于搜索目标元素，还具有许多变种问题，比如搜索目标元素的插入位置。

无重复元素的情况

Q&A(1)

1
2
3
给定一个长度为 𝑛 的有序数组 nums 和一个元素 target ，数组不存在重复元素。现将 target
插入到数组 nums 中，并保持其有序性。若数组中已存在元素 target ，则插入到其左方。请返
回插入后 target 在数组中的索引。

BAvMXOSKbrXnYZww-567494a7-d982-0637-3bec-28fddb73591a|738

[!NOTE] 当数组中包含 target 时，插入点的索引是否是该元素的索引？
将 target 插入到相等元素的左边，这意味着新插入的 target 替换了原来 target 的位置。也就是说，当数组包含 target 时，插入点的索引就是该target 的索引。

[!NOTE] 当数组中不存在 target 时，插入点是哪个元素的索引？
进一步思考二分查找过程：当 nums[m] < target 时 𝑖 移动，这意味着指针 𝑖 在向大于等于 target 的元素靠近。同理，指针 𝑗 始终在向小于等于 target 的元素靠近。

因此二分结束时一定有：𝑖 指向首个大于 target 的元素，𝑗 指向首个小于 target 的元素。易得当数组不包含target 时，插入索引为 𝑖 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 二分查找插入点（无重复元素）索引返回不插入 */
int binarySearchInsertionSimple(vector<int> &nums, int target) {
	int i = 0, j = nums.size() - 1; // 初始化双闭区间 [0, n-1]
	while (i <= j) {
		int m = i + (j - i) / 2; // 计算中点索引 m
		if (nums[m] < target) {
			i = m + 1; // target 在区间 [m+1, j] 中
		} else if (nums[m] > target) {
			j = m - 1; // target 在区间 [i, m-1] 中
		} else {
			return m; // 找到 target ，返回插入点 m
		}
	}
	// 未找到 target ，返回插入点 i
	return i;
}

Q&A(2)

1
在上一题的基础上，规定数组可能包含重复元素，其余不变。

假设数组中存在多个 target ，则普通二分查找只能返回其中一个 target 的索引，而无法确定该元素的左边和右边还有多少target。

方法一

题目要求将目标元素插入到最左边，所以我们需要查找数组中最左一个 target 的索引。通过以下步骤实现

  1. 执行二分查找，得到任意一个 target 的索引，记为 𝑘 。
  2. 从索引 𝑘 开始，向左进行线性遍历，当找到最左边的 target 时返回。

BAvMXOSKbrXnYZww-219c56a8-80d3-1d29-3339-5c9d39a1b70b|585
此方法虽然可用，但其包含线性查找，因此时间复杂度为 𝑂(𝑛) 。当数组中存在很多重复的 target 时，该方法效率很低。

方法二

拓展二分查找代码，整体流程保持不变，每轮先计算中点索引 𝑚 ，再判断 target 和
nums[m] 大小关系，分为以下几种情况。

  • 当 nums[m] < target 或 nums[m] > target 时，说明还没有找到 target ，因此采用普通二分查找的缩小区间操作，从而使指针 𝑖 和 𝑗 向 target 靠近。
  • 当 nums[m] == target 时，说明小于 target 的元素在区间 [𝑖, 𝑚 − 1] 中，因此采用 𝑗 = 𝑚 − 1 来缩小区间，从而使指针 𝑗 向小于 target 的元素靠近。
    循环完成后，𝑖 指向最左边的 target ，𝑗 指向首个小于 target 的元素，因此索引 𝑖 就是插入点。
    BAvMXOSKbrXnYZww-aae3aabb-e15c-7859-2c86-4f5c6e394c7c|935
    BAvMXOSKbrXnYZww-0775f6ca-1ceb-a9a6-cc3e-287962757144|944
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/* 二分查找插入点（存在重复元素） */
int binarySearchInsertion(vector<int> &nums, int target) {
	int i = 0, j = nums.size() - 1; // 初始化双闭区间 [0, n-1]
	while (i <= j) {
		int m = i + (j - i) / 2; // 计算中点索引 m
		if (nums[m] < target) {
			i = m + 1; // target 在区间 [m+1, j] 中
		} else if (nums[m] > target) {
			j = m - 1; // target 在区间 [i, m-1] 中
		} else {
			j = m - 1; // 首个小于 target 的元素在区间 [i, m-1] 中
		}
	}
	// 返回插入点 i
	return i;
}

二分查找边界

Q&A(左边界)

1
2
给定一个长度为 𝑛 的有序数组 nums ，数组可能包含重复元素。请返回数组中最左一个元素
target 的索引。若数组中不包含该元素，则返回−1。

回忆二分查找插入点的方法，搜索完成后 𝑖 指向最左一个 target ，因此查找插入点本质上是在查找最左一个target 的索引。

考虑通过查找插入点的函数实现查找左边界。请注意，数组中可能不包含 target ，这种情况可能导致以下两种结果。

  • 插入点的索引 𝑖 越界。
  • 元素 nums[i] 与 target 不相等。

当遇到以上两种情况时，直接返回−1即可。

1
2
3
4
5
6
7
8
9
10
11
/* 二分查找最左一个 target */
int binarySearchLeftEdge(vector<int> &nums, int target) {
	// 等价于查找 target 的插入点
	int i = binarySearchInsertion(nums, target);
		// 未找到 target ，返回 -1
	if (i == nums.size() || nums[i] != target) {
		return -1;
	}
	// 找到 target ，返回索引 i
	return i;
}

右边界

复用查找左边界

实际上，我们可以利用查找最左元素的函数来查找最右元素，具体方法为：将查找最右一个 target 转化为查找最左一个 target + 1。
查找完成后，指针 𝑖 指向最左一个 target + 1（如果存在），而 𝑗 指向最右一个 target ，因
此返回 𝑗 即可。
BAvMXOSKbrXnYZww-a4068b6b-47b5-0bc9-1352-55372b95a4ce|734
请注意，返回的插入点是 𝑖 ，因此需要将其减 1 ，从而获得 𝑗 。

1
2
3
4
5
6
7
8
9
10
11
12
13
/* 二分查找最右一个 target */
int binarySearchRightEdge(vector<int> &nums, int target) {
	// 转化为查找最左一个 target + 1
	int i = binarySearchInsertion(nums, target + 1);
	// j 指向最右一个 target ，i 指向首个大于 target 的元素
	int j = i - 1;
	// 未找到 target ，返回 -1
	if (j == -1 || nums[j] != target) {
		return -1;
	}
	// 找到 target ，返回索引 j
	return j;
}

转化为查找元素

我们知道，当数组不包含 target 时，最终 𝑖 和 𝑗 会分别指向首个大于、小于 target 的元素。
因此，如图所示，我们可以构造一个数组中不存在的元素，用于查找左右边界。

  • 查找最左一个 target ：可以转化为查找 target - 0.5 ，并返回指针 𝑖 。
  • 查找最右一个 target ：可以转化为查找 target + 0.5 ，并返回指针 𝑗 。
    BAvMXOSKbrXnYZww-ca491a44-f595-b5fd-e9af-37f7434c88a6|707
    注意以下两点。
  • 给定数组不包含小数，这意味着我们无须关心如何处理相等的情况。
  • 因为该方法引入了小数，所以需要将函数中的变量 target 改为浮点数类型。