二进制搜索范围内的多个项目（日志时间过滤器）

Question

我有一个日志项数组，已按时间戳（自 1970 年以来的毫秒数）排序。现在我想按特定时间范围过滤它们，所以我想到了二进制搜索，但是这个变体与我之前知道的所有变体都不同，因为我需要在一个范围内找到一个范围。请注意，值边缘可能有 none 或多个项目。

我想出了这个来减少一个范围要求，但仍然不知道如何到达 first/last 边缘项目：

    filterByTime(min: number, max: number): LogItem[] {
        const items = this.items;
        const len = items.length;

        if (min === undefined && max === undefined) {
            return items.slice(0, len - 1);
        }
        min = min || Number.MIN_VALUE;
        max = max || Number.MAX_VALUE;

        const fn = (a: LogItem) => {
            if (a.time < min) {
                return -1;
            } else if (a.time > max) {
                return 1;
            } else {
                return 0;
            }
        };

        const lowerBound = this.binarySearchBound(fn, 0, len, true);
        if (lowerBound == -1) { return []; }

        const upperBound = this.binarySearchBound(fn, 0, len, false);

        return items.slice(lowerBound, upperBound + 1);
    }

    binarySearchBound(compareFn: (a: LogItem) => number, left: number, right: number, isLowerBound: boolean): number {
        const items = this.items;
        if (items.length == 0) {
            return -1;
        }

        if (isLowerBound && compareFn(items[0]) == 0) {
            return 0;
        } else if (!isLowerBound && compareFn(items[items.length - 1]) == 0) {
            return items.length - 1;
        }

        while (left <= right) {
            const mid = (left + right) / 2;
            const item = this.items[mid];

            const compare = compareFn(item);
            if (compare < 0) {
                left = mid + 1;
            } else if (compare > 0) {
                right = mid - 1;
            } else {
                // What to do now?
            }
        }

        return -1;
    }

最坏的情况，我可以从边缘进行线性搜索，因为我可以假设边缘没有那么很多项目，但肯定有更好的方法我没想到，但是如果 mid 落在结果集的中间，我可能不得不遍历整个结果集。

编辑以添加注释：min 或 max 可能是 undefined（也可能两者都是，在这种情况下我可以设置一个 if和 return 整个数组的副本）。如果 MIN_VALUE 和 MAX_VALUE 是 undefined，是不是更好，还是有更好的方法来处理这种情况？

Answer 1

合并变体 on this article，我将 first 和 last 代码合并为一个函数：

    filterByTime(items: LogItem[], min: number, max: number): LogItem[] {
        const len = items.length;

        if (len == 0) {
            return [];
        }

        if (min === undefined && max === undefined) {
            return items.slice(0, len - 1);
        }
        min = min || Number.MIN_VALUE;
        max = max || Number.MAX_VALUE;

        const fn = (a: LogItem) => {
            if (a.time < min) {
                return -1;
            } else if (a.time > max) {
                return 1;
            } else {
                return 0;
            }
        };

        const lowerBound = this.binarySearchBound(fn, 0, len, true);
        if (lowerBound == -1) { return []; }

        const upperBound = this.binarySearchBound(fn, 0, len, false);

        return items.slice(lowerBound, upperBound + 1);
    }


    binarySearchBound(compareFn: (a: LogItem) => number, left: number, right: number, isLowerBound: boolean): number {
        const items = this.items;
        if (items.length == 0) {
            return -1;
        }

        if (isLowerBound && compareFn(items[0]) == 0) {
            return 0;
        } else if (!isLowerBound && compareFn(items[items.length - 1]) == 0) {
            return items.length - 1;
        }

        let result = -1;
        while (left <= right) {
            const mid = (left + right) / 2;
            const item = this.items[mid];

            const compare = compareFn(item);
            if (compare < 0) {
                left = mid + 1;
            } else if (compare > 0) {
                right = mid - 1;
            } else {
                result = mid;

                if (isLowerBound) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }

        return result;
    }

Answer 2

我建议如下：

编写两个二进制搜索函数，因为执行时间不会因传递和检查 isLowerBound 布尔值而受到阻碍。
使返回的upperBound表示属于该范围的潜在最后一个索引之后的下一个索引。这对应于参数如何与 slice.
等本机函数一起使用
不要使用-1 作为特殊索引。如果编码得当，一个空范围将以任何方式从两个二进制搜索中出来，并给出一个空数组作为结果
使比较函数使用 2 个参数，因此您实际上可以搜索 min 或 max 值。
是的，我会使用 MIN_VALUE 和 MAX_VALUE 作为默认值，而不测试边界情况。如果边界情况经常发生，可能值得包括这些检查，但通常要注意，这些检查随后将针对每个过滤器执行，这可能会降低平均执行时间。

这里是使用整数数据（而不是对象）的建议实现，以保持简单。为了在片段中包含它运行我还删除了类型引用：

function filterByTime(min=Number.MIN_VALUE, max=Number.MAX_VALUE) {
    const fn = (a, b) => a - b; // simplified (should be a.time - b.time)

    const lowerBound = this.binarySearchLowerBound(fn, 0, this.items.length, min);
    const upperBound = this.binarySearchUpperBound(fn, lowerBound, this.items.length, max);

    return this.items.slice(lowerBound, upperBound);
}

function binarySearchLowerBound(compareFn, left, right, target) {
    while (left < right) {
        const mid = (left + right) >> 1;
        if (compareFn(this.items[mid], target) < 0) {
            left = mid + 1;
        } else { // Also when equal...
            right = mid;
        }
    }
    return left;
}

function binarySearchUpperBound(compareFn, left, right, target) {
    while (left < right) {
        const mid = (left + right) >> 1;
        if (compareFn(this.items[mid], target) <= 0) { // Also when equal...
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

// Demo with simplified data (instead of objects with time property)
this.items = [1, 2, 2, 2, 3, 4, 4, 5, 5, 5, 6, 7, 8, 8];
console.log(this.filterByTime(2, 4));
console.log(this.filterByTime(4, 5));

二进制搜索范围内的多个项目（日志时间过滤器）

Binary Search for multiple items within a Range (Log time filter)

javascript

algorithm

binary-search

typescript