二进制搜索-多个搜索值

Question

我使用二进制搜索来搜索应在我的应用中呈现的行范围。 GridRow具有3个属性：top，height和bottom，并对行列表进行排序。

示例：

我在下一行30px和rowBinarySearch中将140传递给我的第一个firstIndex调用，以加快搜索速度。我返回lastIndex + 1以获取数组最后一行的可见性：

const firstIndex = rowBinarySearch(rows, 30);
const lastIndex = rowBinarySearch(rows, 140, firstIndex);

return range.slice(firstIndex, lastIndex + 1);

搜索功能实现：

function rowBinarySearch(arr: GridRow[], val: number, start = 0, end = arr.length - 1): number {
    const mid = Math.floor((start + end) / 2);
    if (mid < 0)
        return 0;
    if (val === arr[mid].top)
        return mid;
    if (start >= end)
        return mid; // original version should return -1 if element dont exist
    return val < arr[mid].top
        ? rowBinarySearch(arr, val, start, mid - 1)
        : rowBinarySearch(arr, val, mid + 1, end);
}

预期的行为：1.删​​除上面评论列表中评论的hacky返回2.查找第一行，该行的top值低于搜索的值3.如果不应该将lastIndex增加1

，那就太好了

感谢您的帮助：）

Answer 1

1. 删除上面评论列表中评论的hacky返回

这不是恶意的回报。递归算法始终需要一个基本情况，而start >= end正是该递归所依赖的基本情况。

不是前面的return，这是不常规的。如果val允许使用所有整数值，则val === arr[mid].top是极少数情况，并且实际上不需要特殊处理。想想val为arr[mid].top + 1时会发生什么。它应该相同（假设height大于1）。

也不需要return时的第一个mid < 0，除非您计划为start或end使用负值调用此函数。因此，在递归调用中冒着对end执行此操作的风险，但是请参阅下一节如何避免这种情况。

2. 找到第一行该行的最高值低于搜索的值

当前，您的算法不正确：在第二次调用中传递120而不是140时，返回值少2个单位，而您仅“爬”一行。

我建议将end定义为当前范围的第一个索引之后。这与为.slice之类的函数定义参数的方式是一致的。

3. 如果不应该将lastIndex增加1，那将是很棒的事情>

您不应该这样做，因为只有在您使用相同的函数查找开始行和结束行的情况下才希望选择比lastIndex - firstIndex多的行，这是合乎逻辑的。因此，只需添加1，不必担心。

这里是固定算法：

function rowBinarySearch(arr, val, start = 0, end = arr.length) {
    if (start >= end) return end - 1; // base case
    const mid = (start + end) >> 1; // Use shift, so you don't need to `floor`.
    return val < arr[mid].top
        ? rowBinarySearch(arr, val, start, mid)
        : rowBinarySearch(arr, val, mid + 1, end);
}

// Demo
const rows = Array.from({length: 7}, (_, id) => ({
    id, top: id*25, bottom: id*25+25, height: 25
}));
const firstIndex = rowBinarySearch(rows, 30);
const lastIndex = rowBinarySearch(rows, 140, firstIndex);
console.log(rows.slice(firstIndex, lastIndex + 1).map(JSON.stringify).join("\n"));