Recursive Binary Search in Typescript

Question

I've ran a few tests, not extensive though, and it apparently works. Like many standard binary search algorithms, if the number returned is < 0, you can take the complement (~) of the returned value to find the insert point, eg const ix = bs(arr, 5); // ~ix is the insertion point

interface bsRange {
    min: number;
    max: number;
}

const bs = (arr: number[], value: number, range: bsRange | null = null): number => {
    if (!range) range = {
        min: 0, max: arr.length - 1
    };

    const indexToCheck = Math.floor((range.min + range.max) / 2);
    const iValue = arr[indexToCheck];
    if (value === iValue) return indexToCheck;

    if (range.max === range.min) {
        // we're at the last element to check
        if (iValue > value) {
            return ~(range.max);
        } else {
            return ~(range.max) - 1;
        }
    }


    if (value < iValue) {
        range.max = indexToCheck - 1;
    } else if (value > iValue) {
        range.min = indexToCheck + 1;
    }

    return bs(arr, value, range);
};
```

Answer 1

Your code looks good to me. I just stumbled over the range parameter, which feels unusual to me. But if you remove it, you have to combine the result for the upper half of the considered array.

const bs = (arr: number[], value: number): number => {
    const indexToCheck = Math.floor((arr.length - 1) / 2);
    const iValue = arr[indexToCheck];

    if (value === iValue) return indexToCheck;
    if (arr.length === 1) return (iValue > value) ? ~0 : ~1;
    if (value < iValue) return bs(arr.slice(0, indexToCheck), value)

    const subResult = bs(arr.slice(indexToCheck + 1), value);
    return subResult >= 0
        ? indexToCheck + 1 + subResult
        : ~(indexToCheck + 1 + ~subResult)
};