10.1 二分查找¶
二分查找(binary search)是一种基于分治策略的高效搜索算法。它利用数据的有序性,每轮缩小一半搜索范围,直至找到目标元素或搜索区间为空为止。
Question
给定一个长度为 \(n\) 的数组 nums ,元素按从小到大的顺序排列且不重复。请查找并返回元素 target 在该数组中的索引。若数组不包含该元素,则返回 \(-1\) 。示例如图 10-1 所示。
图 10-1 二分查找示例数据
图解 10-1:二分查找的示例输入
用柱状图与数组方格对照展示有序数组和查找目标。
给定严格递增的有序数组 nums = [1, 3, 6, 8, 12, 15, 23, 26, 31, 35],索引从 0 到 9,查找目标元素 target = 6。
画面上半部分“使用柱状图表示数组”:从左到右排列十根高度递增的竖柱,每根柱子顶部标出对应元素值;柱状图下方标出从 0 到 9 的“索引”;下半部分用十个横向连续的数组方格展示同一数组。上下两部分之间由双向箭头连接,表明柱状图与一维数组完全等价。
位于索引 2 的元素 6 在上方柱状图和下方数组方格中都用青色高亮标出:其左侧是索引 0、1 的较小元素 1、3,右侧依次是索引 3 至 9 的较大元素 8、12、15、23、26、31、35。本图仅定义输入数据与查找目标,尚未展开二分折半步骤。
查找成功应返回目标所在的索引 2。
如图 10-2 所示,我们先初始化指针 \(i = 0\) 和 \(j = n - 1\) ,分别指向数组首元素和尾元素,代表搜索区间 \([0, n - 1]\) 。请注意,中括号表示闭区间,其包含边界值本身。
接下来,循环执行以下两步。
- 计算中点索引 \(m = \lfloor {(i + j) / 2} \rfloor\) ,其中 \(\lfloor \: \rfloor\) 表示向下取整操作。
- 判断
nums[m]和target的大小关系,分为以下三种情况。- 当
nums[m] < target时,说明target在区间 \([m + 1, j]\) 中,因此执行 \(i = m + 1\) 。 - 当
nums[m] > target时,说明target在区间 \([i, m - 1]\) 中,因此执行 \(j = m - 1\) 。 - 当
nums[m] = target时,说明找到target,因此返回索引 \(m\) 。
- 当
若数组不包含目标元素,搜索区间最终会缩小为空。此时返回 \(-1\) 。
图 10-2 二分查找流程
图解 10-2:二分查找
在升序数组中查找目标值 6,每轮比较中点元素后排除不可能包含目标的一半区间。
输入为含 10 个互异元素的升序数组,索引从 0 到 9,查找目标值 target = 6;各索引对应的元素见输入表。
指针 i、j 分别表示当前搜索闭区间 [i, j] 的左、右边界(两端点均包含在搜索范围内);m 表示区间中点索引,按 (i + j) / 2 向下取整计算。每轮先计算中点 m,再比较 nums[m] 与目标值。
共 7 个画面:先初始化,再演示 3 轮比较。每轮将“计算中点”和“比较后缩小区间或命中”分开展示;虚线框表示当前搜索区间。
| 索引 | 元素值 |
|---|---|
| 0 | 1 |
| 1 | 3 |
| 2 | 6 |
| 3 | 8 |
| 4 | 12 |
| 5 | 15 |
| 6 | 23 |
| 7 | 26 |
| 8 | 31 |
| 9 | 35 |
初始化搜索区间
令 i = 0、j = 9,搜索闭区间 [0, 9] 覆盖全部 10 个元素,左右端点的值分别为 1、35;此时尚未计算中点 m。
第 1 轮:计算中点 m = 4
在闭区间 [0, 9](i = 0、j = 9)内,m = (0 + 9) / 2 向下取整得 4,指向元素 12。下一步将它与目标 6 比较。
第 1 轮:12 大于 6,右边界移到 3
在原区间 [0, 9] 中,中点 m = 4 的值 12 大于目标 6。数组升序,所以索引 4 及其右侧都不可能命中;令 j = m - 1 = 3。现在 i = 0、j = 3,区间为 [0, 3],剩余 [1, 3, 6, 8];旧指针 m 仍指向区间外的索引 4(值 12),尚未重新计算。
第 2 轮:计算中点 m = 1
在闭区间 [0, 3](i = 0、j = 3)内,m = (0 + 3) / 2 向下取整得 1,指向元素 3。下一步将它与目标 6 比较。
第 2 轮:3 小于 6,左边界移到 2
在原区间 [0, 3] 中,中点 m = 1 的值 3 小于目标 6。数组升序,所以索引 1 及其左侧都不可能命中;令 i = m + 1 = 2。现在 i = 2、j = 3,区间为 [2, 3],剩余 [6, 8];旧指针 m 仍指向区间外的索引 1(值 3),尚未重新计算。
第 3 轮:计算中点 m = 2
在闭区间 [2, 3](i = 2、j = 3)内,m = (2 + 3) / 2 向下取整得 2,与左边界 i 重合,指向元素 6。下一步将它与目标 6 比较。
第 3 轮:命中目标,返回索引 2
中点 m = 2 的值 6 等于目标 6,查找结束。最终画面只保留指向索引 2 的中点指针 m,边界指针 i、j 和区间虚线框均已隐藏。
依次比较中点元素 12、3、6,第三次比较命中目标,返回的是索引 2,而不是元素值 6。
值得注意的是,由于 \(i\) 和 \(j\) 都是 int 类型,因此 \(i + j\) 可能会超出 int 类型的取值范围。为了避免大数越界,我们通常采用公式 \(m = \lfloor {i + (j - i) / 2} \rfloor\) 来计算中点。
代码如下所示:
def binary_search(nums: list[int], target: int) -> int:
"""二分查找(双闭区间)"""
# 初始化双闭区间 [0, n-1] ,即 i, j 分别指向数组首元素、尾元素
i, j = 0, len(nums) - 1
# 循环,当搜索区间为空时跳出(当 i > j 时为空)
while i <= j:
# 理论上 Python 的数字可以无限大(取决于内存大小),无须考虑大数越界问题
m = (i + j) // 2 # 计算中点索引 m
if nums[m] < target:
i = m + 1 # 此情况说明 target 在区间 [m+1, j] 中
elif nums[m] > target:
j = m - 1 # 此情况说明 target 在区间 [i, m-1] 中
else:
return m # 找到目标元素,返回其索引
return -1 # 未找到目标元素,返回 -1
/* 二分查找(双闭区间) */
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 binarySearch(int[] nums, int target) {
// 初始化双闭区间 [0, n-1] ,即 i, j 分别指向数组首元素、尾元素
int i = 0, j = nums.length - 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 BinarySearch(int[] nums, int target) {
// 初始化双闭区间 [0, n-1] ,即 i, j 分别指向数组首元素、尾元素
int i = 0, j = nums.Length - 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;
}
/* 二分查找(双闭区间) */
func binarySearch(nums []int, target int) int {
// 初始化双闭区间 [0, n-1] ,即 i, j 分别指向数组首元素、尾元素
i, j := 0, len(nums)-1
// 循环,当搜索区间为空时跳出(当 i > j 时为空)
for i <= j {
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
}
/* 二分查找(双闭区间) */
func binarySearch(nums: [Int], target: Int) -> Int {
// 初始化双闭区间 [0, n-1] ,即 i, j 分别指向数组首元素、尾元素
var i = nums.startIndex
var j = nums.endIndex - 1
// 循环,当搜索区间为空时跳出(当 i > j 时为空)
while i <= j {
let 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
}
/* 二分查找(双闭区间) */
function binarySearch(nums, target) {
// 初始化双闭区间 [0, n-1] ,即 i, j 分别指向数组首元素、尾元素
let i = 0,
j = nums.length - 1;
// 循环,当搜索区间为空时跳出(当 i > j 时为空)
while (i <= j) {
// 计算中点索引 m ,使用 parseInt() 向下取整
const m = parseInt(i + (j - i) / 2);
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;
}
/* 二分查找(双闭区间) */
function binarySearch(nums: number[], target: number): number {
// 初始化双闭区间 [0, n-1] ,即 i, j 分别指向数组首元素、尾元素
let i = 0,
j = nums.length - 1;
// 循环,当搜索区间为空时跳出(当 i > j 时为空)
while (i <= j) {
// 计算中点索引 m
const m = Math.floor(i + (j - i) / 2);
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;
}
}
return -1; // 未找到目标元素,返回 -1
}
/* 二分查找(双闭区间) */
int binarySearch(List<int> nums, int target) {
// 初始化双闭区间 [0, n-1] ,即 i, j 分别指向数组首元素、尾元素
int i = 0, j = nums.length - 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;
}
/* 二分查找(双闭区间) */
fn binary_search(nums: &[i32], target: i32) -> i32 {
// 初始化双闭区间 [0, n-1] ,即 i, j 分别指向数组首元素、尾元素
let mut i = 0;
let mut j = nums.len() as i32 - 1;
// 循环,当搜索区间为空时跳出(当 i > j 时为空)
while i <= j {
let m = i + (j - i) / 2; // 计算中点索引 m
if nums[m as usize] < target {
// 此情况说明 target 在区间 [m+1, j] 中
i = m + 1;
} else if nums[m as usize] > target {
// 此情况说明 target 在区间 [i, m-1] 中
j = m - 1;
} else {
// 找到目标元素,返回其索引
return m;
}
}
// 未找到目标元素,返回 -1
return -1;
}
/* 二分查找(双闭区间) */
int binarySearch(int *nums, int len, int target) {
// 初始化双闭区间 [0, n-1] ,即 i, j 分别指向数组首元素、尾元素
int i = 0, j = len - 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;
}
/* 二分查找(双闭区间) */
fun binarySearch(nums: IntArray, target: Int): Int {
// 初始化双闭区间 [0, n-1] ,即 i, j 分别指向数组首元素、尾元素
var i = 0
var j = nums.size - 1
// 循环,当搜索区间为空时跳出(当 i > j 时为空)
while (i <= j) {
val 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
}
### 二分查找(双闭区间) ###
def binary_search(nums, target)
# 初始化双闭区间 [0, n-1] ,即 i, j 分别指向数组首元素、尾元素
i, j = 0, nums.length - 1
# 循环,当搜索区间为空时跳出(当 i > j 时为空)
while i <= j
# 理论上 Ruby 的数字可以无限大(取决于内存大小),无须考虑大数越界问题
m = (i + j) / 2 # 计算中点索引 m
if nums[m] < target
i = m + 1 # 此情况说明 target 在区间 [m+1, j] 中
elsif nums[m] > target
j = m - 1 # 此情况说明 target 在区间 [i, m-1] 中
else
return m # 找到目标元素,返回其索引
end
end
-1 # 未找到目标元素,返回 -1
end
可视化运行
时间复杂度为 \(O(\log n)\) :在二分循环中,区间每轮缩小一半,因此循环次数为 \(\log_2 n\) 。
空间复杂度为 \(O(1)\) :指针 \(i\) 和 \(j\) 使用常数大小空间。
10.1.1 区间表示方法¶
除了上述双闭区间外,常见的区间表示还有“左闭右开”区间,定义为 \([0, n)\) ,即左边界包含自身,右边界不包含自身。在该表示下,区间 \([i, j)\) 在 \(i = j\) 时为空。
我们可以基于该表示实现具有相同功能的二分查找算法:
def binary_search_lcro(nums: list[int], target: int) -> int:
"""二分查找(左闭右开区间)"""
# 初始化左闭右开区间 [0, n) ,即 i, j 分别指向数组首元素、尾元素+1
i, j = 0, len(nums)
# 循环,当搜索区间为空时跳出(当 i = j 时为空)
while i < j:
m = (i + j) // 2 # 计算中点索引 m
if nums[m] < target:
i = m + 1 # 此情况说明 target 在区间 [m+1, j) 中
elif nums[m] > target:
j = m # 此情况说明 target 在区间 [i, m) 中
else:
return m # 找到目标元素,返回其索引
return -1 # 未找到目标元素,返回 -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;
}
/* 二分查找(左闭右开区间) */
int binarySearchLCRO(int[] nums, int target) {
// 初始化左闭右开区间 [0, n) ,即 i, j 分别指向数组首元素、尾元素+1
int i = 0, j = nums.length;
// 循环,当搜索区间为空时跳出(当 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;
}
/* 二分查找(左闭右开区间) */
int BinarySearchLCRO(int[] nums, int target) {
// 初始化左闭右开区间 [0, n) ,即 i, j 分别指向数组首元素、尾元素+1
int i = 0, j = nums.Length;
// 循环,当搜索区间为空时跳出(当 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;
}
/* 二分查找(左闭右开区间) */
func binarySearchLCRO(nums []int, target int) int {
// 初始化左闭右开区间 [0, n) ,即 i, j 分别指向数组首元素、尾元素+1
i, j := 0, len(nums)
// 循环,当搜索区间为空时跳出(当 i = j 时为空)
for i < j {
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
}
/* 二分查找(左闭右开区间) */
func binarySearchLCRO(nums: [Int], target: Int) -> Int {
// 初始化左闭右开区间 [0, n) ,即 i, j 分别指向数组首元素、尾元素+1
var i = nums.startIndex
var j = nums.endIndex
// 循环,当搜索区间为空时跳出(当 i = j 时为空)
while i < j {
let 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
}
/* 二分查找(左闭右开区间) */
function binarySearchLCRO(nums, target) {
// 初始化左闭右开区间 [0, n) ,即 i, j 分别指向数组首元素、尾元素+1
let i = 0,
j = nums.length;
// 循环,当搜索区间为空时跳出(当 i = j 时为空)
while (i < j) {
// 计算中点索引 m ,使用 parseInt() 向下取整
const m = parseInt(i + (j - i) / 2);
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;
}
/* 二分查找(左闭右开区间) */
function binarySearchLCRO(nums: number[], target: number): number {
// 初始化左闭右开区间 [0, n) ,即 i, j 分别指向数组首元素、尾元素+1
let i = 0,
j = nums.length;
// 循环,当搜索区间为空时跳出(当 i = j 时为空)
while (i < j) {
// 计算中点索引 m
const m = Math.floor(i + (j - i) / 2);
if (nums[m] < target) {
// 此情况说明 target 在区间 [m+1, j) 中
i = m + 1;
} else if (nums[m] > target) {
// 此情况说明 target 在区间 [i, m) 中
j = m;
} else {
// 找到目标元素,返回其索引
return m;
}
}
return -1; // 未找到目标元素,返回 -1
}
/* 二分查找(左闭右开区间) */
int binarySearchLCRO(List<int> nums, int target) {
// 初始化左闭右开区间 [0, n) ,即 i, j 分别指向数组首元素、尾元素+1
int i = 0, j = nums.length;
// 循环,当搜索区间为空时跳出(当 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;
}
/* 二分查找(左闭右开区间) */
fn binary_search_lcro(nums: &[i32], target: i32) -> i32 {
// 初始化左闭右开区间 [0, n) ,即 i, j 分别指向数组首元素、尾元素+1
let mut i = 0;
let mut j = nums.len() as i32;
// 循环,当搜索区间为空时跳出(当 i = j 时为空)
while i < j {
let m = i + (j - i) / 2; // 计算中点索引 m
if nums[m as usize] < target {
// 此情况说明 target 在区间 [m+1, j) 中
i = m + 1;
} else if nums[m as usize] > target {
// 此情况说明 target 在区间 [i, m) 中
j = m;
} else {
// 找到目标元素,返回其索引
return m;
}
}
// 未找到目标元素,返回 -1
return -1;
}
/* 二分查找(左闭右开区间) */
int binarySearchLCRO(int *nums, int len, int target) {
// 初始化左闭右开区间 [0, n) ,即 i, j 分别指向数组首元素、尾元素+1
int i = 0, j = len;
// 循环,当搜索区间为空时跳出(当 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;
}
/* 二分查找(左闭右开区间) */
fun binarySearchLCRO(nums: IntArray, target: Int): Int {
// 初始化左闭右开区间 [0, n) ,即 i, j 分别指向数组首元素、尾元素+1
var i = 0
var j = nums.size
// 循环,当搜索区间为空时跳出(当 i = j 时为空)
while (i < j) {
val 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
}
### 二分查找(左闭右开区间) ###
def binary_search_lcro(nums, target)
# 初始化左闭右开区间 [0, n) ,即 i, j 分别指向数组首元素、尾元素+1
i, j = 0, nums.length
# 循环,当搜索区间为空时跳出(当 i = j 时为空)
while i < j
# 计算中点索引 m
m = (i + j) / 2
if nums[m] < target
i = m + 1 # 此情况说明 target 在区间 [m+1, j) 中
elsif nums[m] > target
j = m - 1 # 此情况说明 target 在区间 [i, m) 中
else
return m # 找到目标元素,返回其索引
end
end
-1 # 未找到目标元素,返回 -1
end
可视化运行
如图 10-3 所示,在两种区间表示下,二分查找算法的初始化、循环条件和缩小区间操作皆有所不同。
由于“双闭区间”表示中的左右边界都被定义为闭区间,因此通过指针 \(i\) 和指针 \(j\) 缩小区间的操作也是对称的。这样更不容易出错,因此一般建议采用“双闭区间”的写法。
图 10-3 两种区间定义
图解 10-3:二分查找的区间约定
右边界指针 j 是否包含在搜索区间内,直接决定 j 的初始值、循环终止条件以及向左收缩时的赋值方式。
示意升序数组包含 n = 10 个元素,索引为 0 至 9;指针 i、j 分别标识当前搜索区间的左、右边界,m 表示当前折半中点索引。图中柱高仅示意元素单调递增,未标注具体元素数值。
左右两图的蓝色虚线框均框住十个元素。左图“双闭区间 [i, j]”的右指针 j 指向最后一根柱子,包含该位置;右图“左闭右开区间 [i, j)”的 j 指向数组最右端外侧,排除该位置。按 n = 10 代入初始化公式,左图 j = 9,右图 j = 10。
当 i = j 时,双闭区间仍有一个待查元素,左闭右开区间却已为空。向左收缩时,双闭区间的右端点包含在区间内,所以用 j = m − 1 排除 m;左闭右开的右端点本就不包含,直接令 j = m。下表列出图中的四项规则,并补充与终止条件相反的 while 循环条件。
| 项目 | 双闭区间 [i, j] | 左闭右开区间 [i, j) |
|---|---|---|
| 初始化 | i = 0,j = n − 1 | i = 0,j = n |
| 循环终止(补充:循环条件) | i > j(while i ≤ j) | i ≥ j(while i < j) |
| 中间值小于目标 | i = m + 1 | i = m + 1 |
| 中间值大于目标 | j = m − 1 | j = m |
两套写法的初始化、循环条件与收缩规则须配套使用;双闭区间的两侧收缩对称。
10.1.2 优点与局限性¶
二分查找在时间和空间方面都有较好的性能。
- 二分查找的时间效率高。在大数据量下,对数阶的时间复杂度具有显著优势。例如,当数据大小 \(n = 2^{20}\) 时,线性查找需要 \(2^{20} = 1048576\) 轮循环,而二分查找仅需 \(\log_2 2^{20} = 20\) 轮循环。
- 二分查找无须额外空间。相较于需要借助额外空间的搜索算法(例如哈希查找),二分查找更加节省空间。
然而,二分查找并非适用于所有情况,主要有以下原因。
- 二分查找仅适用于有序数据。若输入数据无序,为了使用二分查找而专门进行排序,得不偿失。因为排序算法的时间复杂度通常为 \(O(n \log n)\) ,比线性查找和二分查找都更高。对于频繁插入元素的场景,为保持数组有序性,需要将元素插入到特定位置,时间复杂度为 \(O(n)\) ,也是非常昂贵的。
- 二分查找仅适用于数组。二分查找需要跳跃式(非连续地)访问元素,而在链表中执行跳跃式访问的效率较低,因此不适合应用在链表或基于链表实现的数据结构。
- 小数据量下,线性查找性能更佳。在线性查找中,每轮只需 1 次判断操作;而在二分查找中,需要 1 次加法、1 次除法、1 ~ 3 次判断操作、1 次加法(减法),共 4 ~ 6 个单元操作;因此,当数据量 \(n\) 较小时,线性查找反而比二分查找更快。