如何在JavaScript中实现类似Array.find的带回调二分搜索函数？

尝试实现一个功能与Array.find一致的函数，用二分搜索替代循环实现。希望能传入回调函数，调用方式类似：binarySearch(elem => elem.value === 4, data)。但实现时遇到问题：无法确定判断数组中间元素与回调目标值大小关系的条件。相关代码如下：

let data = [
    {value: 1, qwerty: "vika"},
    {value: 6, qwerty: "vika"},
    {value: -7, qwerty: "vika"},
    {value: 14, qwerty: "vika"},
    {value: 0, qwerty: "vika"},
    {value: 8, qwerty: "vika"},
    {value: 6, qwerty: "vika"},
    {value: 3, qwerty: "vika"},
    {value: -99, qwerty: "vika"},
    {value: 99, qwerty: "vika"},
    {value: 4, qwerty: "vika"},
]


data.sort((a,b) => a.value-b.value)

function binarySearch(cb, data) {
    let middle = data[Math.round(data.length/2)]
    let leftPart = data.slice(0, data.length/2)
    let rightPart = data.slice(data.length/2, data.length)
    if (cb(middle)) { return middle }
    else {
        return /*CONDITION FOR DECIDE IS MIDDLE LESS OR MORE THAN VALUE FROM CALLBACK*/
            ? binarySearch(cb, rightPart) : binarySearch(cb, leftPart)
    }
}

console.log(binarySearch(elem => elem.value === 4, data))

请问这种方式是否可以实现二分搜索？

这种方式无法直接实现二分搜索，核心原因在于：二分搜索的本质是依赖数组的有序性，通过判断当前元素与目标值的大小关系（小于/等于/大于）来缩小搜索范围，但你当前传入的回调函数只能返回布尔值（仅告知是否匹配），无法提供「中间元素比目标值大还是小」的方向信息——没有这个方向，就没法确定该往左还是往右继续搜索。

要实现基于二分搜索的查找，必须调整回调的设计，让它能返回比较结果而非单纯的布尔值。最常用的方式是模仿数组排序的 comparator 函数：返回负数、0、正数，分别代表当前元素小于、等于、大于目标值。

修改后的示例代码 #

let data = [
    {value: 1, qwerty: "vika"},
    {value: 6, qwerty: "vika"},
    {value: -7, qwerty: "vika"},
    {value: 14, qwerty: "vika"},
    {value: 0, qwerty: "vika"},
    {value: 8, qwerty: "vika"},
    {value: 6, qwerty: "vika"},
    {value: 3, qwerty: "vika"},
    {value: -99, qwerty: "vika"},
    {value: 99, qwerty: "vika"},
    {value: 4, qwerty: "vika"},
]

data.sort((a,b) => a.value - b.value)

function binarySearch(compareFn, data) {
    // 终止条件：数组为空，说明未找到目标
    if (data.length === 0) return undefined;

    const midIndex = Math.floor(data.length / 2);
    const midElem = data[midIndex];
    const compareResult = compareFn(midElem);

    if (compareResult === 0) {
        // 找到匹配元素
        return midElem;
    } else if (compareResult < 0) {
        // 当前元素小于目标，去右半部分继续搜索
        return binarySearch(compareFn, data.slice(midIndex + 1));
    } else {
        // 当前元素大于目标，去左半部分继续搜索
        return binarySearch(compareFn, data.slice(0, midIndex));
    }
}

// 调用时传入比较函数，返回当前元素与目标值的差值
console.log(binarySearch(elem => elem.value - 4, data));

额外说明 #

除了回调设计的问题，原代码还有两处需要修正的细节：

1. 用Math.floor(data.length / 2)计算中间索引比Math.round更稳妥，避免在某些数组长度下出现索引偏移；
2. 必须添加递归终止条件（数组为空时返回undefined），否则当目标元素不存在时会陷入无限递归。

总结：如果坚持使用仅返回布尔值的回调，无法实现二分搜索。只有让回调提供比较方向的信息，才能利用二分搜索的特性高效缩小搜索范围。

内容的提问来源于stack exchange，提问作者waterically