对范围内的多个项目进行二分搜索（记录时间过滤器）

Question

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

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

    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

并返回整个数组的副本）。如果是

MIN_VALUE

，最好用

MAX_VALUE

和

undefined

代替，还是有更好的方法来处理这种情况？

Answer 1

编写两个二分搜索函数，因为传递和检查
• isLowerBound

  布尔值不会妨碍执行时间。

使返回的
• upperBound

  表示属于该范围的潜在最后一个索引之后的

  next

  索引。这与参数与 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));

Answer 2

，我将

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