binaryInsert.js

function hash() {
    var obj = {};
    setHash(obj, 16);
    setHash(obj, 4);
    setHash(obj, 9);
    setHash(obj, 53);
    setHash(obj, 14);
}

function setHash(obj, id) {
    obj[id] = id;
}

function binaryIndexOf(a, it) {
    var minI = 0;
    var maxI = a.length - 1;
    var cI = 0;
    var cE;
    while (minI <= maxI) {
        cI = (minI + maxI) >> 1;
        cE = a[cI];
        if (cE < it) {
            minI = cI + 1;
        }
        else if (cE > it) {
            maxI = cI - 1;
        }
        else {
            return cI;
        }
    }
    return maxI === cI ? -cI - 2 : -cI - 1;
}
function binaryInsert(a, it) {
    var minI = 0;
    var maxI = a.length - 1;
    var cI = 0;
    var cE;
    while (minI <= maxI) {
        cI = (minI + maxI) >> 1;
        cE = a[cI];
        if (cE < it) {
            minI = cI + 1;
        }
        else if (cE > it) {
            maxI = cI - 1;
        }
        else {
            return true;
        }
    }
    var p = maxI === cI ? cI + 1 : cI;
    for (var i = a.length - 1; i >= p; i--) {
        a[i + 1] = a[i];
    }
    a[p] = it;
}

function insert(a, p, el) {
    for (var i = a.length - 1; i >= p; i--) {
        a[i + 1] = a[i];
    }
    a[p] = el;

}

function assert(arr, ins, dest) {
    var x = binaryIndexOf(arr, ins);
    if (x < 0) {
        insert(arr, -x - 1, ins);
    }
    if (arr.toString() !== dest.toString()) {
        throw new Error(`Expected: ${JSON.stringify(dest)}, Result ${JSON.stringify(arr)}`);
    }
}

function binaryTests(fn) {
    assert([0, 1, 2], 0, [0, 1, 2]);
    assert([0, 1, 2], 1, [0, 1, 2]);
    assert([0, 1, 2], 2, [0, 1, 2]);
    assert([0, 1, 2], 20, [0, 1, 2, 20]);
    assert([0, 1, 2], 3, [0, 1, 2, 3]);
    assert([0, 1, 2], -1, [-1, 0, 1, 2]);
    assert([0, 1, 20], 2, [0, 1, 2, 20]);
    assert([0, 1, 2, 3], 0, [0, 1, 2, 3]);
    assert([0, 1, 2, 3], 1, [0, 1, 2, 3]);
    assert([0, 1, 2, 3], 2, [0, 1, 2, 3]);
    assert([0, 1, 2, 3], 3, [0, 1, 2, 3]);
    assert([0, 1, 2, 3], 4, [0, 1, 2, 3, 4]);
    assert([0, 1, 2, 3], -1, [-1, 0, 1, 2, 3]);
    assert([0, 1, 2, 3], -10, [-10, 0, 1, 2, 3]);
    assert([0, 1, 20, 30], 2, [0, 1, 2, 20, 30]);
    assert([0, 1, 20, 30], 20, [0, 1, 20, 30]);
    assert([0, 1, 20, 30], 30, [0, 1, 20, 30]);
    assert([0, 1, 20, 30], 4, [0, 1, 4, 20, 30]);
    assert([-1, 0, 1, 20, 30], -1, [-1, 0, 1, 20, 30]);
    assert([-1, 0, 1, 20, 30], -2, [-2, -1, 0, 1, 20, 30]);
    assert([-1, 0, 1, 20, 30], -20, [-20, -1, 0, 1, 20, 30]);
    assert([1, 2, 3], 1, [1, 2, 3]);
}

// binaryTests(binaryIndexOf);


var arr = [];
arr[0] = 16;
arr[1] = 4;
arr[2] = 9;
arr[3] = 53;
arr[4] = 14;

binaryIndexOf([1, 2], 16);

function binary() {
    var arr = [];
    arr[0] = 16;
    arr[1] = 4;
    arr[2] = 9;
    arr[3] = 53;
    arr[4] = 14;
    binaryInsert(arr, 16);
    binaryInsert(arr, 4);
    binaryInsert(arr, 9);
    binaryInsert(arr, 53);

    binaryInsert(arr, 15);
    binaryInsert(arr, 2);
    binaryInsert(arr, 78);
    binaryInsert(arr, 14);
    binaryInsert(arr, 10);
    binaryInsert(arr, 28);
    binaryInsert(arr, 1);
}

function searchAndReplace(arr, item) {
    var x = binaryIndexOf(arr, item);
    if (x < 0) {
        insert(arr, -x - 1, item);
    }
}

function abc() {
    console.time('perf');
    for (var i = 0; i < 1e6; i++) {
        // hash();
        binary();
    }
    console.timeEnd('perf');
}

abc();
// binary();