find insert position for sorted array

bsearch.js

(function() {

    Array.prototype['insertPos'] = function(val, cmp) {
        var lower = 0;
        var upper = this.length - 1;
        var idx = Math.floor((lower + upper) / 2);
        var ret;

        if (this.length === 0) {
            return 0;
        }

        if (cmp === undefined) {
            cmp = function(a, b) {
                if (a < b) {
                    return -1;
                } else if (a > b) {
                    return 1;
                } else {
                    return 0;
                }
            }
        }
        
        for (;;) {
            ret = cmp(val, this[idx]);
            if (ret < 0) {
                upper = idx;
                idx = Math.floor((lower + idx) / 2);
            } else if (ret > 0) {
                lower = idx;
                idx = Math.ceil((idx + upper) / 2);
            } else {
                break;
            }

            if (upper - lower <= 1) {
                if (this[upper] < val) {
                    idx = upper + 1;
                } else if (this[lower] < val) {
                    idx = upper;
                } else {
                    idx = lower;
                }
                break;
            }
        }
        
        return idx;
    };

    function assert(cond, message) {
        if (!cond) {
            throw message || "Assertion failed";
        }
    }

    function test() {
        assert([1].insertPos(0) === 0);
        assert([1].insertPos(1) === 0);
        assert([1].insertPos(2) === 1);
        assert([1,2].insertPos(0) === 0);
        assert([1,2].insertPos(1) === 0);
        assert([1,2].insertPos(2) === 1);
        assert([1,2].insertPos(3) === 2);
        assert([1,2,3,4].insertPos(0) === 0);
        assert([1,2,3,4].insertPos(1) === 0);
        assert([1,2,3,4].insertPos(2) === 1);
        assert([1,2,3,4].insertPos(3) === 2);
        assert([1,2,3,4].insertPos(4) === 3);
        assert([1,2,3,4].insertPos(5) === 4);
        assert([1,3,5,7].insertPos(0) === 0);
        assert([1,3,5,7].insertPos(1) === 0);
        assert([1,3,5,7].insertPos(2) === 1);
        assert([1,3,5,7].insertPos(3) === 1);
        assert([1,3,5,7].insertPos(4) === 2);
        assert([1,3,5,7].insertPos(5) === 2);
        assert([1,3,5,7].insertPos(6) === 3);
        assert([1,3,5,7].insertPos(7) === 3);
        assert([1,3,5,7].insertPos(8) === 4);
        assert([1,3,3,7].insertPos(3) === 1);
        assert([1,3,3,7].insertPos(7) === 3);
        assert([1,3,3,7].insertPos(8) === 4);
        console.log('all tests pass');
    }

    test();
})();