Двоичный поиск - поиск нескольких значений

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. Удалите хакерский возврат, прокомментированный в прокомментированном листинге выше 2. Найдите первую строку, в которой top значение строки ниже, чем искомое значение 3. Было бы здорово, если бы lastIndex не увеличивалось на 1

Спасибо за любую помощь :)

Answer 1

1. Удалить хакерский возврат, прокомментированный в прокомментированном листинге выше

Это не хакерский возврат. Рекурсивный алгоритм всегда нуждается в базовом случае, и start >= end - это именно тот базовый случай, от которого зависит эта рекурсия.

Предыдущее return не является обычным. Если для val разрешены все целочисленные значения, то val === arr[mid].top - редкий случай, и на самом деле он не требует особой обработки. Подумайте, что должно произойти, когда val равно arr[mid].top + 1. Он должен быть таким же (при условии, что height больше 1).

Также первый return, когда mid < 0 не требуется, если вы не планируете вызывать эту функцию с отрицательными значениями для любого start или end. Фактически вы рискуете сделать это для end в рекурсивных вызовах, но посмотрите следующий пункт о том, как этого избежать.

Найдите первую строку, в которой верхнее значение строки ниже искомого значения

В настоящее время ваш алгоритм неверен: когда вместо 140 вы передаете 120 во втором вызове, возвращаемое значение на 2 единицы меньше, в то время как вы "поднимаетесь" только на одну строку.

Я бы предложил определить end как первый индекс после текущего диапазона. Это соответствует определению параметров для таких функций, как .slice.

Было бы здорово, если бы не увеличивать lastIndex на 1

Вы не должны стремиться к этому, поскольку логично, что если вы используете одну и ту же функцию для поиска начального row и конечную строку, вы хотите выбрать еще одну строку, чем 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"));