Binary search in JavaScript

binarySearch.js

function defaultCompare(o1, o2) {
    if (o1 < o2) {
        return -1;
    }
    if (o1 > o2) {
        return 1;
    }
    return 0;
}

/**
 * @param array sorted array with compare func
 * @param item search item
 * @param start (optional) start index
 * @param end (optional) exclusive end index
 * @param compare (optional) custom compare func
 * @param bound (optional) (-1) first index; (1) last index; (0) doesn't matter
 */
function binarySearch(array, item, start, end, compare, bound) {
    if (!compare) {
        compare = defaultCompare;
    }
    let from = start == null ? 0 : start;
    let to = (end == null ? array.length : end) - 1;
    let found = -1;
    while (from <= to) {
        const middle = (from + to) >>> 1;
        const compareResult = compare(array[middle], item);
        if (compareResult < 0) {
            from = middle + 1;
        }
        else if (compareResult > 0) {
            to = middle - 1;
        }
        else if (!bound) {
            return middle;
        }
        else if (bound < 0) {
            // First occurrence:
            found = middle;
            to = middle - 1;
        }
        else {
            // Last occurrence:
            found = middle;
            from = middle + 1;
        }
    }
    return found >= 0 ? found : -from - 1;
}

binarySearch.test.js

describe('binarySearch', function () {
	it('stress test', function () {
		const indexToItem = index => `item${(index + 2).toString().padStart(3, '0')}`
		const arr = new Array(51).fill(0).map((o, i) => indexToItem(i) + (i % 2 ? '_' : ''))
		for (let index = -2; index < arr.length + 2; index++) {
			const item = indexToItem(index)
			for (let bound = -1; bound < 1; bound++) {
				for (let start = -1; start <= Math.min(arr.length - 1, Math.max(0, index)); start++) {
					for (let end = arr.length; end >= Math.min(arr.length, index + 1); end--) {
						const result = binarySearch(
							arr,
							item,
							start < 0 ? null : start,
							end >= arr.length ? null : end,
							// eslint-disable-next-line no-nested-ternary
							index % 3 ? (o1, o2) => (o1 > o2 ? 1 : o1 < o2 ? -1 : 0) : null,
							bound
						)

						const log = JSON.stringify({
							index,
							start,
							end,
							bound
						})

						if (index < 0) {
							assert.strictEqual(result, ~0, log)
						} else if (index >= arr.length) {
							assert.strictEqual(result, ~arr.length, log)
						} else if (index % 2) {
							assert.strictEqual(result, ~index, log)
						} else {
							assert.strictEqual(result, index, log)
						}
					}
				}
			}
		}
	})

	it('specific', function () {
		assert.strictEqual(binarySearch([], 0), ~0)
		assert.strictEqual(binarySearch([1], 0), ~0)
		assert.strictEqual(binarySearch([-1], 0), ~1)
		assert.strictEqual(binarySearch([0], 0), 0)
		assert.strictEqual(binarySearch([0, 1, 1, 1, 2], 1, null, null, null, -1), 1)
		assert.strictEqual(binarySearch([0, 1, 1, 1, 2], 1, null, null, null, 1), 3)
		assert.strictEqual(binarySearch([0, 0, 1, 1, 1, 2], 1, null, null, null, -1), 2)
		assert.strictEqual(binarySearch([0, 0, 1, 1, 1, 2], 1, null, null, null, 1), 4)
		assert.strictEqual(binarySearch([0, 0, 1, 1, 1], 1, null, null, null, -1), 2)
		assert.strictEqual(binarySearch([0, 0, 1, 1, 1], 1, null, null, null, 1), 4)
		assert.strictEqual(binarySearch([1, 1, 1], 1, null, null, null, -1), 0)
		assert.strictEqual(binarySearch([1, 1, 1], 1, null, null, null, 1), 2)
	})
})