编辑“︁二分搜索”︁

{{DISPLAYTITLE:二分搜索}}

'''二分搜索'''（Binary Search）是一种在'''有序数组'''中高效查找特定元素的算法，其时间复杂度为<math>O(\log n)</math>，远优于线性搜索的<math>O(n)</math>。它是计算机科学中最基础且广泛应用的算法之一，适用于排序后的数据集合。

== 算法原理 ==
二分搜索通过反复将搜索区间减半来定位目标值。具体步骤如下：
1. 初始化两个指针：<code>left</code>（指向数组起始）和<code>right</code>（指向数组末尾）。
2. 计算中间索引<code>mid = left + (right - left) // 2</code>（避免整数溢出）。
3. 比较中间元素与目标值：
   * 若相等，返回索引。
   * 若中间元素小于目标值，调整<code>left = mid + 1</code>。
   * 若中间元素大于目标值，调整<code>right = mid - 1</code>。
4. 重复步骤2-3，直到<code>left > right</code>（未找到目标）。

=== 可视化流程 ===
<mermaid>
graph TD
    A[数组: 2, 5, 8, 12, 16, 23, 38, 56, 72, 91] --> B[目标: 23]
    B --> C{比较中间元素}
    C -->|mid=16 < 23| D[搜索右半部分: 23, 38, 56, 72, 91]
    D --> E{新的中间元素}
    E -->|mid=56 > 23| F[搜索左半部分: 23, 38]
    F --> G{找到23, 返回索引5}
</mermaid>

== 代码实现 ==
以下是Python实现示例：

<syntaxhighlight lang="python">
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1  # 未找到

# 示例
arr = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91]
target = 23
print(f"索引位置: {binary_search(arr, target)}")  # 输出: 索引位置: 5
</syntaxhighlight>

== 复杂度分析 ==
* '''时间复杂度''': <math>O(\log n)</math> —— 每次迭代将搜索范围减半。
* '''空间复杂度''': <math>O(1)</math> —— 仅需常数空间存储指针。

== 变体与应用 ==
=== 变体示例 ===
1. '''查找第一个/最后一个匹配项''': 修改相等时的处理逻辑。
2. '''旋转有序数组搜索''': 处理部分有序数据（如<code>[4,5,6,1,2,3]</code>）。

=== 实际应用 ===
* '''数据库索引''': B树/B+树中的二分查找加速查询。
* '''游戏开发''': 在排序的分数表中快速定位玩家排名。
* '''数值计算''': 求解方程的近似解（如二分法求根）。

== 常见错误与注意事项 ==
1. '''边界条件''': 确保循环终止条件为<code>left <= right</code>而非<code>left < right</code>。
2. '''整数溢出''': 使用<code>mid = left + (right - left) // 2</code>而非<code>(left + right) // 2</code>。
3. '''未排序输入''': 必须预先排序数组，否则结果无效。

== 练习建议 ==
1. 实现递归版本的二分搜索。
2. 解决LeetCode问题「34. 在排序数组中查找元素的第一个和最后一个位置」。
3. 尝试在非数值数据（如字符串）上应用二分搜索。

{{算法导航}}

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:搜索算法]]