跳到主要内容

二分查找

介绍​

二分查找（Binary Search）是一种高效的搜索算法，用于在有序数组中查找特定元素。它的核心思想是通过不断将搜索范围减半来快速定位目标值。与线性查找相比，二分查找的时间复杂度为 O(log n)，这使得它在处理大规模数据时表现尤为出色。

备注

二分查找的前提是数组必须是有序的（升序或降序）。如果数组无序，需要先进行排序。

算法原理​

二分查找的基本步骤如下：

  1. 初始化：定义两个指针，left 和 right，分别指向数组的起始和末尾位置。
  2. 计算中间位置：计算中间索引 mid = Math.floor((left + right) / 2)。
  3. 比较中间值：
    • 如果 arr[mid] 等于目标值，返回 mid。
    • 如果 arr[mid] 小于目标值，将 left 移动到 mid + 1。
    • 如果 arr[mid] 大于目标值，将 right 移动到 mid - 1。
  4. 重复步骤 2 和 3，直到 left 超过 right。
  5. 返回结果：如果未找到目标值，返回 -1。

以下是一个简单的二分查找流程图：

代码示例​

以下是用 JavaScript 实现的二分查找代码：

javascript
function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (arr[mid] === target) {
            return mid; // 找到目标值，返回索引
        } else if (arr[mid] < target) {
            left = mid + 1; // 目标值在右半部分
        } else {
            right = mid - 1; // 目标值在左半部分
        }
    }

    return -1; // 未找到目标值
}

// 示例
const arr = [1, 3, 5, 7, 9, 11, 13, 15];
const target = 7;
console.log(binarySearch(arr, target)); // 输出: 3

输入和输出​

  • 输入：一个有序数组 arr 和目标值 target。
  • 输出：目标值在数组中的索引（如果存在），否则返回 -1。

实际应用场景​

二分查找广泛应用于需要高效搜索的场景，例如：

  1. 数据库查询：在有序数据集中快速查找记录。
  2. 游戏开发：在有序列表中查找特定元素，如敌人位置或道具。
  3. 算法优化：作为其他算法（如分治算法）的一部分，用于减少时间复杂度。
提示

在实际开发中，二分查找常用于处理大规模数据，例如日志分析、搜索引擎索引等。

总结​

二分查找是一种高效的搜索算法，适用于有序数组。它通过不断将搜索范围减半，将时间复杂度降低到 O(log n)，远优于线性查找的 O(n)。掌握二分查找不仅有助于解决实际问题，还能为学习更复杂的算法打下坚实基础。

附加资源与练习​

  • 练习：

    1. 实现一个递归版本的二分查找。
    2. 尝试在降序数组中实现二分查找。
    3. 编写代码处理数组中存在多个相同目标值的情况，返回第一个或最后一个匹配的索引。

  • 推荐阅读：

    • 《算法导论》中的“分治法”章节。
    • LeetCode 上的二分查找相关题目（如“搜索插入位置”、“寻找峰值”）。
警告

二分查找虽然高效，但仅适用于有序数组。如果数组无序，需要先进行排序，这会增加额外的时间复杂度。