2
\$\begingroup\$

I need your help to see if the following binary search code is correct. I did my best to cover the corner cases. I wonder if I missed anything.

The code as it is with tests (you can play with it online here):

function binarySearch<a, r>(
    hay: a[],
    needle: a,
    compare:(one: a, another: a, oneGreaterThanAnother: () => r, oneLessThanAnother: () => r, oneEqualToAnother: () => r) => r,
    haveStaightHit: (hay: a[], index: number) => r,
    haveExpectedToBeAt: (hay: a[], index: number) => r
) {
    if (hay.length > 0) {
        return binarySearchUnsafe(hay, needle, 0, hay.length - 1, compare, haveStaightHit, haveExpectedToBeAt);
    } else {
        return haveExpectedToBeAt(hay, 0);
    }
}
function binarySearchUnsafe<a, r>(
    hay: a[],
    needle: a,
    from: number,
    to: number,
    compare:(one: a, another: a, oneGreaterThanAnother: () => r, oneLessThanAnother: () => r, oneEqualToAnother: () => r) => r,
    haveStaightHit: (hay: a[], index: number) => r,
    haveExpectedToBeAt: (hay: a[], index: number) => r
): r {
    if (from < to) {
        var at = from + (~~((to - from) / 2));
        return compare(
            needle,
            hay[at],
            function needleIsOnTheRight() {
                return binarySearchUnsafe(hay, needle, at + 1, to, compare, haveStaightHit, haveExpectedToBeAt);
            },
            function needleIsOnTheLeft() {
                return binarySearchUnsafe(hay, needle, from, at, compare, haveStaightHit, haveExpectedToBeAt);
            },
            function needleIsFound() {
                return haveStaightHit(hay, at);
            }
        );      
    } else if (from > to) {
        throw new Error('From index ' + from + ' is bigger than the to index ' + to + '.');
    } else {
        var at = from /* === to */;
        return compare(
            needle,
            hay[at],
            function needleIsOnTheRight() {
                return haveExpectedToBeAt(hay, at + 1);
            },
            function needleIsOnTheLeft() {
                return haveExpectedToBeAt(hay, at);             
            },
            function needleIsFound() {
                return haveStaightHit(hay, at)
            }
        );
    }
}

function areEqual(actual: any, expected: any) {
    if (actual !== expected) throw new Error('Expected: ' + expected + ', Actual: ' + actual);
}

function compareStrings<r>(one: string, another: string, oneGreaterThanAnother: () => r, oneLessThanAnother: () => r, oneEqualToAnother: () => r) : r {
    if (one > another) {
        return oneGreaterThanAnother();
    } else if (one < another) {
        return oneLessThanAnother();
    } else {
        return oneEqualToAnother();
    }
}

function failOver(message: string) : any {
    return function() {
        throw new Error(message);
    }
}

try {
    binarySearch([], 'x', compareStrings, failOver('Direct hit is not expected.'), (hay, index) => areEqual(index, 0));
    binarySearch(['b', 'd', 'f'], 'b', compareStrings, (hay, index) => areEqual(index, 0), failOver('Direct hit is expected.'));
    binarySearch(['b', 'd', 'f'], 'd', compareStrings, (hay, index) => areEqual(index, 1), failOver('Direct hit is expected.'));
    binarySearch(['b', 'd', 'f'], 'f', compareStrings, (hay, index) => areEqual(index, 2), failOver('Direct hit is expected.'));
    binarySearch(['b', 'd', 'f'], 'g', compareStrings, failOver('Direct hit is not expected.'), (hay, index) => areEqual(index, 3));
    binarySearch(['b', 'd', 'f'], 'a', compareStrings, failOver('Direct hit is not expected.'), (hay, index) => areEqual(index, 0));
    binarySearch(['b', 'd', 'f'], 'c', compareStrings, failOver('Direct hit is not expected.'), (hay, index) => areEqual(index, 1));
    alert('You are all good!');
} catch (e) {
    alert(e.message);
}
\$\endgroup\$

1 Answer 1

Reset to default
3
\$\begingroup\$

That looks jolly complicated. If you haven't read it, look for Jon Bentley's Programming Pearls article on binary search. Here's my version:

var bSearch = <T>(xs: T[], x: T, cmp: (p: T, q: T) => number): number => {
    var bot = 0;
    var top = xs.length;
    while (bot < top) { // If x is in xs, it's somewhere in xs[bot..top).
        var mid = Math.floor((bot + top) / 2);
        var c = cmp(xs[mid], x);
        if (c === 0) return mid;
        if (c < 0) bot = mid + 1;
        if (0 < c) top = mid; 
    }
    return -1;
}

var cmp = (p: number, q: number) => p - q;

console.log(bSearch([], 3, cmp) === -1);
console.log(bSearch([3], 3, cmp) === 0);
console.log(bSearch([1, 3], 3, cmp) === 1);
console.log(bSearch([3, 4], 3, cmp) === 0);
console.log(bSearch([3, 3], 3, cmp) !== -1);
console.log(bSearch([1, 2, 3], 3, cmp) === 2);
console.log(bSearch([1, 3, 4], 3, cmp) === 1);
console.log(bSearch([3, 4, 5], 3, cmp) === 0);
console.log(bSearch([4, 5, 6], 3, cmp) === -1);
\$\endgroup\$
9
  • \$\begingroup\$ Its not complicated, its just in a functional style. If the elemen isn't found my search results to the best expected position, yours always gets -1. \$\endgroup\$ Commented Feb 4, 2014 at 2:35
  • \$\begingroup\$ @bonomo, I'm a well seasoned functional programmer and I'm afraid I don't recognise the functional style in your approach. It would be trivial to rewrite my implementation as a recursive function, if that's what you'd prefer to see. Similarly, one could always return mid rather than -1 on failure to indicate a lower bound on where x "should" be. \$\endgroup\$ Commented Feb 4, 2014 at 2:44
  • \$\begingroup\$ en.m.wikibooks.org/wiki/Haskell/YAHT/… \$\endgroup\$ Commented Feb 4, 2014 at 2:57
  • \$\begingroup\$ If you always return mid you would have no way to tell apart a straight hit from a miss. \$\endgroup\$ Commented Feb 4, 2014 at 2:58
  • \$\begingroup\$ @bonomo, sure you do -- you just look up the item at the returned index. Was it the one you were looking for? Yes: hooray! No: that's where it would go. \$\endgroup\$ Commented Feb 4, 2014 at 3:20

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.