折半查找法（二分查找）

定义与基本思想

折半查找法（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

时间复杂度分析

• 最好情况：$O(1)$
• 最坏/平均情况：$O(\log_2 n)$

练习题

练习 1

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

参考答案

解题思路：每次折半，比较中间元素。

详细步骤：

1. $low=0, high=5, mid=2, A[2]=5 < 7$
2. $low=3, high=5, mid=4, A[4]=9 > 7$
3. $low=3, high=3, mid=3, A[3]=7$，找到目标

答案：$7$ 在数组下标 $3$ 处。

练习 2

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

参考答案

解题思路：考查折半查找的前提和效率。

详细步骤：

1. 适用于有序表
2. 时间复杂度为 $O(\log_2 n)$

答案：适用于有序表，时间复杂度 $O(\log_2 n)$。

考研真题

真题 1

【2017·408】折半查找法的查找过程是如何进行的？其查找效率如何？

参考答案

解题思路：描述查找流程和效率。

详细步骤：

1. 每次比较中间元素，缩小一半区间
2. 最多比较 $\log_2 n$ 次

答案：每次折半，效率 $O(\log_2 n)$。