二分查找实现

描述

二分查找（Binary Search）是一种在有序数组中查找目标的算法。每次将搜索范围缩小一半，时间复杂度 O(log n)。

核心原理

1. 数组必须有序
2. 每次取中间元素比较
3. 根据大小关系缩小搜索范围
4. 直到找到目标或范围为空

实现代码

基础版

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;
}

完整版（处理边界情况）

function binarySearch(arr, target, compareFn) {
    if (!arr || arr.length === 0) {
        return -1;
    }

    let left = 0;
    let right = arr.length - 1;

    const defaultCompare = (a, b) => {
        if (a < b) return -1;
        if (a > b) return 1;
        return 0;
    };

    const compare = compareFn || defaultCompare;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        const result = compare(arr[mid], target);

        if (result === 0) {
            return mid;
        } else if (result < 0) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

递归版

function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
    if (left > right) {
        return -1;
    }

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

    if (arr[mid] === target) {
        return mid;
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, target, mid + 1, right);
    } else {
        return binarySearchRecursive(arr, target, left, mid - 1);
    }
}

查找左边界（第一个 >= target）

function lowerBound(arr, target) {
    let left = 0;
    let right = arr.length;

    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left;
}

查找右边界（最后一个 <= target）

function upperBound(arr, target) {
    let left = 0;
    let right = arr.length;

    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left - 1;
}

使用示例

const sortedArray = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];

console.log(binarySearch(sortedArray, 9)); // 4（索引位置）
console.log(binarySearch(sortedArray, 6)); // -1（不存在）

// 查找左边界
console.log(lowerBound(sortedArray, 8)); // 4（第一个 >= 8 的位置）

// 查找右边界
console.log(upperBound(sortedArray, 8)); // 3（最后一个 <= 8 的位置）

复杂度分析

指标	复杂度
时间复杂度	O(log n)
空间复杂度（迭代）	O(1)
空间复杂度（递归）	O(log n)

二分查找 vs 线性查找

特性	二分查找	线性查找
时间复杂度	O(log n)	O(n)
数组要求	有序	无需有序
实现难度	较复杂	简单
数据量大的场景	高效	低效