Binary Search Performance (v2)

Revision 2 of this benchmark created on

Preparation HTML

<script src="https://cdn.jsdelivr.net/npm/lodash@4.17.21/lodash.min.js"></script>

Setup

// generate 10k ordered elements
const range = _.range(10000);
// drop an element with 33.33% chance
const _1_3 = 1 / 3;
const values = _.filter(range, () => Math.random() > _1_3);
const testCases = _.shuffle(_.map(range, () => _.random(10000)));

function binarySearchV1(val, ar) {
    let i = 0;
    let j = ar.length - 1;

    while (i <= j) {
        const k = Math.floor((i + j) / 2);

        if (ar[k] < val) {
            i = k + 1;
        } else if (ar[k] > val) {
            j = k - 1;
        } else {
            return k;
        }
    }

    return i;
}

function binarySearchV2(val, ar) {
    let i = 0;
    let j = ar.length - 1;

    while (i <= j) {
        const k = ((i + j) / 2) | 0;

        if (ar[k] === val) {
            return k;
        } else if (ar[k] < val) {
            i = k + 1;
        } else {
            j = k - 1;
        }
    }

    return i;
}

Test runner

Ready to run.

Testing in
TestOps/sec
Standard
for (const testCase of testCases) {
	binarySearchV1(testCase, values);
}
ready
Bitwise floor
for (const testCase of testCases) {
	binarySearchV2(testCase, values);
}
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.