Search code examples
javascriptarraystypescriptalgorithmbinary-search

Binary search - multiple searched values

I using binary search for searching rows range that should be rendered in my app. GridRow has 3 properties: top, height and bottom and list of rows is sorted.

Example:

I passing 30px to my first call of rowBinarySearch, in next line 140 and firstIndex to speedup search. I return lastIndex + 1 for fix visibility of last row in my array:

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

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

diagram

Search function implementation:

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

Expected behavior: 1. Remove hacky return commented in commented listing above 2. Find first row that top value of row is lower then searched value 3. I would be great if shouldnt increment lastIndex by 1

Thanks for any help :)

Solution
    1. Remove hacky return commented in commented listing above

    This is not a hacky return. A recursive algorithm always needs a base case, and start >= end is exactly the base case this recursion depends on.

    It is the preceding return that is not conventional. If all integer values are allowed for val, then val === arr[mid].top is a rare case, and it does not need special treatment really. Think of what should happen when val is arr[mid].top + 1. It should be the same (assuming a height of more than 1).

    Also the first return for when mid < 0 is not necessary, unless you plan to call this function with negative values for either start or end. And acutally you risk to do this for end in recursive calls, but see next point on how to avoid that.

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

    Currently, your algorithm is not correct: when instead of 140, you pass 120 in the second call, the return value is 2 units less, while you only "climb" one row.

    I would suggest defining end as the first index after the current range. This is in line with how parameters are defined for functions like .slice.

    1. I would be great if shouldnt increment lastIndex by 1

    You should not strive to do that, since it is only logical that if you use the same function for both finding the starting row and the ending row, that you want one more row selected than lastIndex - firstIndex. So just add 1 and don't worry about it.

    Here is a fixed algorithm:

    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"));