JavaScript 二分查找实现

问题

在有序数组中查找指定值，返回该值的索引位置。

解答

二分查找（折半查找）通过不断将查找区间对半分割来定位目标值。每次比较中间元素，根据大小关系决定在左半部分还是右半部分继续查找，直到找到目标或区间为空。

非递归实现

// arr: 有序数组; key: 查找的元素
function search(arr, key) {
    let start = 0;
    let end = arr.length - 1;
    
    while (start <= end) {
        // 取中间索引
        const mid = Math.floor((start + end) / 2);
        
        if (key === arr[mid]) {
            return mid; // 找到目标，返回索引
        } else if (key < arr[mid]) {
            end = mid - 1; // 在左半部分查找
        } else {
            start = mid + 1; // 在右半部分查找
        }
    }
    
    return -1; // 未找到
}

递归实现

// arr: 有序数组; key: 查找的元素; start: 开始索引; end: 结束索引
function search2(arr, key, start = 0, end = arr.length - 1) {
    // 查找区间为空，未找到
    if (start > end) {
        return -1;
    }
    
    const mid = Math.floor((start + end) / 2);
    
    if (key === arr[mid]) {
        return mid;
    } else if (key < arr[mid]) {
        return search2(arr, key, start, mid - 1);
    } else {
        return search2(arr, key, mid + 1, end);
    }
}

使用示例

const arr = [1, 3, 5, 7, 9, 11, 13, 15];

console.log(search(arr, 7));  // 3
console.log(search(arr, 10)); // -1

console.log(search2(arr, 9));  // 4
console.log(search2(arr, 2));  // -1

关键点

• 数组必须是有序的，否则无法使用二分查找
• 时间复杂度 O(log n)，比线性查找 O(n) 快得多
• 每次将查找区间缩小一半，通过比较中间元素决定查找方向
• 适用于查找频繁但修改较少的场景，因为插入删除会破坏有序性
• 注意边界条件：start <= end 和 start > end 的判断