折半查找法(二分查找)
折半查找法(Binary Search)是一种高效的查找方法,适用于有序表。其基本思想是:每次将查找范围折半,逐步缩小查找区间,直到找到目标元素或区间为空。
点击“执行一步”观察算法状态变化。
- 适用于有序的线性表(顺序存储或链式存储)
- 数据量较大、查找频繁的场合
- 设查找区间为
- 计算中间位置
- 若 ,查找成功
- 若 ,则在右半区间查找
- 若 ,则在左半区间查找
- 直到 ,查找失败
伪代码如下:
low = 0, high = n-1
while low <= high:
mid = (low + high) // 2
if A[mid] == x:
return mid
elif A[mid] < x:
low = mid + 1
else:
high = mid - 1
return -1
// 折半查找(递归实现,要求 A[0..n-1] 递增有序)
int BinarySearch(int A[], int low, int high, int key) {
if (low > high) return -1; // 查找失败
int mid = (low + high) / 2;
if (A[mid] == key) return mid; // 查找成功
else if (A[mid] < key)
return BinarySearch(A, mid + 1, high); // 右半区间
else
return BinarySearch(A, low, mid - 1); // 左半区间
}
折半查找的过程可以用一棵判定树描述:每个结点代表一次比较的中间位置 mid。
- 判定树是一棵平衡二叉树(或接近平衡),结点数等于表长 n
- 查找成功的最长比较次数 = 判定树的高度
- 平均查找长度约为
以 为例,判定树高度为 ,各层结点数分别为 1、2、4、4,则:
即查找成功平均需要比较 3 次。
- 最好情况:
- 最坏/平均情况:
- 空间复杂度:递归实现 ,迭代实现
实际应用中常需要查找边界位置,这类”二分查找变体”是面试高频题:
| 变体 | 查找目标 |
|---|---|
| 第一个等于 key 的位置 | 左边界 |
| 最后一个等于 key 的位置 | 右边界 |
| 第一个大于等于 key 的位置 | 下界(lower_bound) |
| 第一个大于 key 的位置 | 上界(upper_bound) |
实现要点:找到目标后不立即返回,而是继续向一侧收缩区间。
习题 1
给定有序数组 ,用折半查找法查找元素 的位置。
解题思路:
本题考查折半查找的执行过程。折半查找每次取当前查找区间的中间元素与目标比较,依据比较结果把区间缩小为左半或右半,直到命中目标或区间为空。
详细步骤:
- ,找到目标
最终答案:
在数组下标 处。
习题 2
折半查找法的适用条件是什么?其时间复杂度是多少?
解题思路:
本题考查折半查找的前提条件与效率。折半查找每一步都依赖“中间元素与目标的大小关系”来决定舍弃哪一半区间,这一判断只有在查找表按关键字有序时才成立。
详细步骤:
- 适用于有序表
- 时间复杂度为
- 补充:若表无序,中间的比较结果无法判定目标在左半还是右半,必须先排序或改用顺序查找;由于每次查找把区间缩小一半,最多比较 次。
最终答案:
适用于有序表,时间复杂度 。
习题 3
折半查找法的查找过程是如何进行的?其查找效率如何?
解题思路:
本题要求描述折半查找的流程并给出其效率。流程可归纳为“取中点—比较—缩半”的循环,效率则由区间每轮减半直接导出。
详细步骤:
- 每次比较中间元素,缩小一半区间
- 最多比较 次
- 流程归纳:令 ,若 等于目标则查找成功,否则按比较结果令 或 后继续,直到 判定查找失败。
最终答案:
每次折半,效率 。
