JavaScript中二分查找有哪些常见变体？如何实现这些变体算法

二分查找是针对于有序数组的高效搜索算法，核心逻辑是通过不断缩小搜索区间来定位目标元素，时间复杂度为O(logn)。但在实际业务场景中，我们往往需要处理更复杂的搜索需求，比如查找目标值第一次出现的位置、最后一次出现的位置、第一个大于目标值的元素等，这些需求都可以通过基础二分查找调整边界判断逻辑来实现，也就是二分查找的变体形式。

基础二分查找回顾

在讲解变体之前，先回顾标准二分查找的实现逻辑，后续变体都是在此基础上调整边界收缩规则。

// 标准二分查找，返回目标值在数组中的索引，不存在返回-1
function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    while (left <= right) {
        // 计算中间索引，避免(left+right)溢出
        const mid = left + Math.floor((right - left) / 2);
        if (arr[mid] === target) {
            return mid;
        } else if (arr[mid] < target) {
            // 目标在右半区间，收缩左边界
            left = mid + 1;
        } else {
            // 目标在左半区间，收缩右边界
            right = mid - 1;
        }
    }
    return -1;
}

常见二分查找变体实现

变体1：查找目标值首次出现的位置

当数组中存在多个重复的目标值时，标准二分查找返回的是任意一个匹配位置的索引，而该变体需要返回第一个匹配的位置。

// 查找目标值第一次出现的索引，不存在返回-1
function findFirstOccurrence(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    let result = -1;
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        if (arr[mid] === target) {
            // 记录当前匹配位置，继续向左搜索是否有更早的匹配
            result = mid;
            right = mid - 1;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

变体2：查找目标值最后一次出现的位置

该变体用于返回数组中目标值最后一次出现的索引，逻辑和查找首次出现位置类似，只是匹配到目标值后向右收缩区间。

// 查找目标值最后一次出现的索引，不存在返回-1
function findLastOccurrence(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    let result = -1;
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        if (arr[mid] === target) {
            // 记录当前匹配位置，继续向右搜索是否有更晚的匹配
            result = mid;
            left = mid + 1;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

变体3：查找第一个大于等于目标值的元素

该变体适用于需要找到数组中第一个不小于目标值的元素场景，比如插入排序中确定元素的插入位置。

// 查找第一个大于等于目标值的元素索引，不存在返回-1
function findFirstGreaterOrEqual(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    let result = -1;
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        if (arr[mid] >= target) {
            // 记录当前符合条件的位置，继续向左搜索是否有更小的符合条件的元素
            result = mid;
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }
    return result;
}

变体4：查找最后一个小于等于目标值的元素

该变体用于找到数组中最后一个不大于目标值的元素，常用于范围查询的场景。

// 查找最后一个小于等于目标值的元素索引，不存在返回-1
function findLastLessOrEqual(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    let result = -1;
    while (left <= right) {
        const mid = left + Math.floor((right - left) / 2);
        if (arr[mid] <= target) {
            // 记录当前符合条件的位置，继续向右搜索是否有更大的符合条件的元素
            result = mid;
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return result;
}

变体实现的注意事项

实现二分查找变体时，最核心的是明确边界收缩的规则，避免陷入死循环或者返回错误结果。需要注意以下几点：

• 中间索引的计算要使用left + Math.floor((right - left) / 2)，避免直接相加导致数值溢出。
• 匹配到目标值后，不要直接返回，而是根据变体需求收缩对应的边界，继续搜索更符合条件的位置。
• 循环条件通常使用left <= right，保证所有可能的区间都被遍历到。
• 提前定义结果变量，在符合条件时更新，避免遗漏匹配的位置。

测试验证

我们可以通过一组测试用例验证上述变体的正确性：

const testArr = [1, 2, 2, 2, 3, 4, 4, 5];
console.log(findFirstOccurrence(testArr, 2)); // 输出1
console.log(findLastOccurrence(testArr, 2));  // 输出3
console.log(findFirstGreaterOrEqual(testArr, 3)); // 输出4
console.log(findLastLessOrEqual(testArr, 3)); // 输出4
console.log(findFirstGreaterOrEqual(testArr, 6)); // 输出-1

通过上述测试可以看到，各个变体都能正确返回符合需求的结果，开发者可以根据实际业务场景选择合适的变体实现。

JavaScript二分查找变体搜索算法二分查找修改时间：2026-06-29 23:24:38