js实现二分查找

二分查找的基本原理

二分查找是一种高效的搜索算法，适用于已排序的数组。通过每次将搜索范围减半，快速定位目标值的位置。时间复杂度为 O(log n)。

实现步骤

初始化指针 定义左指针 left 初始为 0，右指针 right 初始为数组长度减 1。

循环条件 当 left 小于等于 right 时，计算中间索引 mid，取 Math.floor((left + right) / 2)。

比较中间值 若中间值等于目标值，直接返回 mid。若中间值小于目标值，调整 left 为 mid + 1；否则调整 right 为 mid - 1。

未找到处理 循环结束后仍未找到目标值，返回 -1 或其他标识符。

代码示例

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

边界条件处理

空数组检查 在函数开始处添加对空数组的判断，直接返回 -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;
    return arr[mid] < target 
        ? binarySearchRecursive(arr, target, mid + 1, right)
        : binarySearchRecursive(arr, target, left, mid - 1);
}

性能优化

位运算计算中点 使用 (left + right) >>> 1 替代 Math.floor，避免浮点数运算，提升速度。

提前终止 在特定场景下，如重复元素中寻找第一个或最后一个匹配项，可调整比较逻辑提前终止循环。

实际应用示例

const sortedArray = [1, 3, 5, 7, 9];
console.log(binarySearch(sortedArray, 5)); // 输出: 2
console.log(binarySearch(sortedArray, 10)); // 输出: -1

注意事项

数组必须有序 二分查找要求输入数组严格升序或降序排列，否则结果不可预测。

大数处理 left + right 可能溢出，使用 left + (right - left) / 2 更安全。