折半查找法（二分查找）

定义与基本思想

折半查找法（Binary Search）是一种高效的查找方法，适用于有序表。其基本思想是：每次将查找范围折半，逐步缩小查找区间，直到找到目标元素或区间为空。

折半查找法（Binary Search）演示

1357911

下一步

适用场景

• 适用于有序的线性表（顺序存储或链式存储）
• 数据量较大、查找频繁的场合

算法描述

1. 设查找区间为 $[low, high]$
2. 计算中间位置 $mid = \lfloor (low + high) / 2 \rfloor$
3. 若 $A[mid] = x$，查找成功
4. 若 $A[mid] < x$，则在右半区间查找
5. 若 $A[mid] > x$，则在左半区间查找
6. 直到 $low > high$，查找失败

伪代码如下：

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
• 查找成功的最长比较次数 = 判定树的高度 $= \lceil \log_2(n+1) \rceil$
• 平均查找长度约为 $ASL \approx \log_2(n+1) - 1$

以 $n=11$ 为例，判定树高度为 $\lceil \log_2 12 \rceil = 4$，各层结点数分别为 1、2、4、4，则：

$ASL = \frac{1\times1 + 2\times2 + 3\times4 + 4\times4}{11} = \frac{1+4+12+16}{11} = \frac{33}{11} = 3$

即查找成功平均需要比较 3 次。

时间复杂度分析

• 最好情况：$O(1)$
• 最坏/平均情况：$O(\log_2 n)$
• 空间复杂度：递归实现 $O(\log n)$，迭代实现 $O(1)$

二分查找的变体

实际应用中常需要查找边界位置，这类”二分查找变体”是面试高频题：

实现要点：找到目标后不立即返回，而是继续向一侧收缩区间。

习题

习题 1

给定有序数组 $A = [1, 3, 5, 7, 9, 11]$，用折半查找法查找元素 $7$ 的位置。

习题 2

折半查找法的适用条件是什么？其时间复杂度是多少？

习题 3

折半查找法的查找过程是如何进行的？其查找效率如何？

上一章节分块查找法介绍分块查找法的基本思想、算法流程、复杂度分析及典型习题。

下一章节哈希表查找介绍哈希表查找的基本思想、哈希函数、冲突处理、复杂度分析及典型习题。