二进制搜索 - 多个搜索值

Question

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

示例：

我在下一行 140 和 firstIndex 中将 30px 传递给我第一次调用 rowBinarySearch 以加快搜索速度。我 return 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 return 2. 找到第一行 top 行的值低于搜索值 3. 如果不应该将 lastIndex 增加 1

，我会很棒

感谢您的帮助:)

Answer 1

Remove hacky return commented in commented listing above

这不是一个 hacky return。递归算法总是需要一个基本情况，而 start >= end 正是这个递归所依赖的基本情况。

就是前面的return不符合常规。如果 val 允许所有整数值，那么 val === arr[mid].top 是一种罕见的情况，实际上不需要特殊处理。想想当 val 是 arr[mid].top + 1 时会发生什么。它应该是相同的（假设 height 大于 1）。

此外，当 mid < 0 时的第一个 return 不是必需的，除非您计划用负值调用此函数 start 或 end。实际上，在递归调用中，您冒着为 end 执行此操作的风险，但请参阅下一点以了解如何避免这种情况。

Find first row that top value of row is lower then searched value

目前，您的算法不正确：当您在第二次调用中传递 120 而不是 140 时，return 值少了 2 个单位，而您只有 "climb" 一行。

我建议将 end 定义为当前范围之后的第一个索引。这与为 .slice.

等函数定义参数的方式一致

I would be great if shouldnt increment lastIndex by 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"));

二进制搜索 - 多个搜索值

Binary search - multiple searched values

javascript

arrays

algorithm

binary-search

typescript