binarySearch.js

/**
 * Find a number in an ordered list of numbers. It does cheap detection for common invalid input:
 * * Argument types
 * * An incorrectly sorted list (descending)
 * * An unsorted list
 * @param  {number}        x   - The "needle" for which to search
 * @param  {array<number>} arr - The list to search
 * @return {number} - The (first) index where `x` occurs in `arr`, or `-1` when not found.
 * @example
 * binarySearch(2, [-1, 0, 0.5, 0.75, 1, 2, 5, 10]);	// 5
 * binarySearch(3, [-1, 0, 0.5, 0.75, 1, 2, 5, 10]);	// -1
 * binarySearch(3, [-1, 0, 0.5, 0.75, '1', 2, 5, 10]);	// -1
 * binarySearch(1, [-1, 0, 0.5, 0.75, '1', 2, 5, 10]);	// TypeError
 * binarySearch(1, [-1, 0.75, 0.5, 0, 5, 2, 1, 10]);	// Error (unsorted)
 * binarySearch(2, [-1, 0.75, 0.5, 0, 5, 2, 1, 10]);	// 5
 */
function binarySearch(x, arr) {
	if (typeof x !== 'number') throw new TypeError('First argument must be a number');
	if (!Array.isArray(arr)) throw new TypeError('Second argument must be an array');

	let low = 0;
	let top = arr.length - 1;
	let mid = 0;
	let pElm;
	let pMid;

	let first = arr[low];
	let last = arr[top];
	
	if (first > last) {
		throw new Error('Array must be sorted in ascending order (smallest to largest).');
	}
	if (first > x || last < x) return -1; // won't be found

	while (top >= low) {
		mid = Math.floor((top + low) / 2);

		let elm = arr[mid];

		if (typeof elm !== 'number') {
			throw new TypeError(`Array elements must be numbers, but got ${JSON.stringify(elm)}.`);
		}

		if (
			typeof pElm !== 'undefined'
		) {
			if (
				(
					pMid > mid		// going up
					&& elm > pElm	// "smaller" number is actually bigger
				)
				|| (
					pMid < mid		// going down
					&& elm < pElm	// "bigger" number is actually smaller
				)
			) throw new Error('Array must be sorted in ascending order (smallest to largest).');
		}

		if (elm === x) {
			return mid;
		}

		if (x > elm) {
			low = mid + 1;
		} else {
			top = mid - 1;
		}

		pElm = elm;
		pMid = mid;
	}

	return -1; // not found
}