Cleanroom binary search challenge

binary-search.js

/*
Cleanroom binary search challenge
Write a binary search, correct the first time, without testing. They say it's harder that it sounds.
https://reprog.wordpress.com/2010/04/19/are-you-one-of-the-10-percent/
*/

// Binary search
// Obnoxiously careful - if there's any mistake here I fail the challenge
// Putting all my thought process as comments so you can make fun

const getMidPoint = (start, end) => {
	// Yes I'm abstracting this into a function so I can reason about it more carefully
	// Yes this is ridiculous but so is pretending we're writing punch cards in 2020

	// n n -> n: but that can't happen, `end` is exclusive

	// 0 1 -> 0
	// (len-1) len -> (2len - 1)/2 = len - 1
	// n (n+1) -> (2n+1)/2 = n: if bounds are touching there's only 1 to try

	// 0 2 -> 1
	// (len-2) len -> (2len - 2)/2 = len - 1
	// n (n+2) -> n+1
	// n (n+2k) -> (2n+2k)/2 = n+k: good, finds the middle
	// n (n+2k+1) -> (2n+2k+1)/2 = n+k: looks ok

	return Math.floor((start + end) / 2);
};

const binSearch = (haystack, needle) => {
	let startIndex = 0; // lowest where needle might be (inclusive)
	let endIndex = haystack.length; // highest where needle can't be (exclusive)
	let midIndex;
	let midValue;

	while (startIndex < endIndex) { // strict because endIndex is exclusive
		midIndex = getMidPoint(startIndex, endIndex);
		midValue = haystack[midIndex];

		if (midValue === needle) { // found
			return midIndex;
		}

		if (midValue < needle) { // needle is towards end of array
			// startIndex is inclusive: +1 to exclude midIndex
			startIndex = midIndex + 1;
		} else { // needle is towards start of array
			// endIndex is exclusive: +0 excludes midIndex
			endIndex = midIndex;
		}
	}

	return -1;
};

// Unit tests
// Wasn't super careful about the test cases, some may be wrong or redundant
// I'll still consider the challenge a pass if there's a mistake below this line

const testCases = [
	// Length 0
	{
		haystack: [],
		needle: 42,
		expected: [-1]
	},
	// Length 1
	{
		haystack: [0],
		needle: 42,
		expected: [-1]
	},
	{
		haystack: [100],
		needle: 42,
		expected: [-1]
	},
	{
		haystack: [42],
		needle: 42,
		expected: [0]
	},
	// Length 2
	{
		haystack: [0, 1],
		needle: 42,
		expected: [-1]
	},
	{
		haystack: [0, 100],
		needle: 42,
		expected: [-1]
	},
	{
		haystack: [50, 100],
		needle: 42,
		expected: [-1]
	},
	{
		haystack: [42, 100],
		needle: 42,
		expected: [0]
	},
	{
		haystack: [1, 42],
		needle: 42,
		expected: [1]
	},
	{
		haystack: [42, 42],
		needle: 42,
		expected: [0, 1]
	},
	// Length 3
	{
		haystack: [0, 1, 100],
		needle: 42,
		expected: [-1]
	},
	{
		haystack: [42, 50, 100],
		needle: 42,
		expected: [0]
	},
	{
		haystack: [0, 42, 100],
		needle: 42,
		expected: [1]
	},
	{
		haystack: [0, 1, 42],
		needle: 42,
		expected: [2]
	},
	{
		haystack: [42, 42, 100],
		needle: 42,
		expected: [0, 1]
	},
	{
		haystack: [0, 42, 42],
		needle: 42,
		expected: [1, 2]
	},
	{
		haystack: [42, 42, 42],
		needle: 42,
		expected: [0, 1, 2]
	},
	// Length 4
	{
		haystack: [1, 2, 3, 4],
		needle: 42,
		expected: [-1]
	},
	{
		haystack: [1, 2, 3, 4],
		needle: 1,
		expected: [0]
	},
	{
		haystack: [1, 2, 3, 4],
		needle: 2,
		expected: [1]
	},
	{
		haystack: [1, 2, 3, 4],
		needle: 3,
		expected: [2]
	},
	{
		haystack: [1, 2, 3, 4],
		needle: 4,
		expected: [3]
	},
	{
		haystack: [1, 1, 2, 3],
		needle: 1,
		expected: [0, 1]
	},
	{
		haystack: [1, 2, 2, 3],
		needle: 2,
		expected: [1, 2]
	},
	{
		haystack: [1, 1, 2, 2],
		needle: 2,
		expected: [2, 3]
	},
	// Length 5
	{
		haystack: [1, 2, 3, 4, 5],
		needle: 42,
		expected: [-1]
	},
	{
		haystack: [1, 2, 3, 4, 5],
		needle: 1,
		expected: [0]
	},
	{
		haystack: [1, 2, 3, 4, 5],
		needle: 2,
		expected: [1]
	},
	{
		haystack: [1, 2, 3, 4, 5],
		needle: 3,
		expected: [2]
	},
	{
		haystack: [1, 2, 3, 4, 5],
		needle: 4,
		expected: [3]
	},
	{
		haystack: [1, 2, 3, 4, 5],
		needle: 5,
		expected: [4]
	},
	{
		haystack: [1, 1, 2, 3, 4],
		needle: 1,
		expected: [0, 1]
	},
	{
		haystack: [1, 2, 2, 3, 4],
		needle: 2,
		expected: [1, 2]
	},
	{
		haystack: [1, 2, 3, 3, 4],
		needle: 3,
		expected: [2, 3]
	},
	{
		haystack: [1, 2, 3, 4, 4],
		needle: 4,
		expected: [3, 4]
	},
	{
		haystack: [1, 1, 1, 2, 3],
		needle: 1,
		expected: [0, 1, 2]
	},
	{
		haystack: [1, 2, 2, 2, 3],
		needle: 2,
		expected: [1, 2, 3]
	},
	{
		haystack: [1, 2, 3, 3, 3],
		needle: 3,
		expected: [2, 3, 4]
	},
	// Length 6
	{
		haystack: [1, 2, 3, 4, 5, 6],
		needle: 42,
		expected: [-1]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6],
		needle: 1,
		expected: [0]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6],
		needle: 2,
		expected: [1]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6],
		needle: 3,
		expected: [2]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6],
		needle: 4,
		expected: [3]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6],
		needle: 5,
		expected: [4]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6],
		needle: 6,
		expected: [5]
	},
	// Length 7
	{
		haystack: [1, 2, 3, 4, 5, 6, 7],
		needle: 42,
		expected: [-1]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7],
		needle: 1,
		expected: [0]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7],
		needle: 2,
		expected: [1]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7],
		needle: 3,
		expected: [2]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7],
		needle: 4,
		expected: [3]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7],
		needle: 5,
		expected: [4]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7],
		needle: 6,
		expected: [5]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7],
		needle: 7,
		expected: [6]
	},
	// Length 8
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8],
		needle: 42,
		expected: [-1]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8],
		needle: 1,
		expected: [0]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8],
		needle: 2,
		expected: [1]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8],
		needle: 3,
		expected: [2]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8],
		needle: 4,
		expected: [3]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8],
		needle: 5,
		expected: [4]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8],
		needle: 6,
		expected: [5]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8],
		needle: 7,
		expected: [6]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8],
		needle: 8,
		expected: [7]
	},
	// Length 9
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9],
		needle: 42,
		expected: [-1]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9],
		needle: 1,
		expected: [0]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9],
		needle: 2,
		expected: [1]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9],
		needle: 3,
		expected: [2]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9],
		needle: 4,
		expected: [3]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9],
		needle: 5,
		expected: [4]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9],
		needle: 6,
		expected: [5]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9],
		needle: 7,
		expected: [6]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9],
		needle: 8,
		expected: [7]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9],
		needle: 9,
		expected: [8]
	},
	// Length 10
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
		needle: 42,
		expected: [-1]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
		needle: 1,
		expected: [0]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
		needle: 2,
		expected: [1]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
		needle: 3,
		expected: [2]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
		needle: 4,
		expected: [3]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
		needle: 5,
		expected: [4]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
		needle: 6,
		expected: [5]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
		needle: 7,
		expected: [6]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
		needle: 8,
		expected: [7]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
		needle: 9,
		expected: [8]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
		needle: 10,
		expected: [9]
	},
	// Length 11
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],
		needle: 42,
		expected: [-1]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],
		needle: 1,
		expected: [0]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],
		needle: 2,
		expected: [1]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],
		needle: 3,
		expected: [2]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],
		needle: 4,
		expected: [3]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],
		needle: 5,
		expected: [4]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],
		needle: 6,
		expected: [5]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],
		needle: 7,
		expected: [6]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],
		needle: 8,
		expected: [7]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],
		needle: 9,
		expected: [8]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],
		needle: 10,
		expected: [9]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11],
		needle: 11,
		expected: [10]
	},
	// Length 12
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],
		needle: 42,
		expected: [-1]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],
		needle: 1,
		expected: [0]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],
		needle: 2,
		expected: [1]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],
		needle: 3,
		expected: [2]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],
		needle: 4,
		expected: [3]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],
		needle: 5,
		expected: [4]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],
		needle: 6,
		expected: [5]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],
		needle: 7,
		expected: [6]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],
		needle: 8,
		expected: [7]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],
		needle: 9,
		expected: [8]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],
		needle: 10,
		expected: [9]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],
		needle: 11,
		expected: [10]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],
		needle: 12,
		expected: [11]
	},
	// Length 20
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
		needle: 42,
		expected: [-1]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
		needle: 1,
		expected: [0]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
		needle: 2,
		expected: [1]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
		needle: 3,
		expected: [2]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
		needle: 4,
		expected: [3]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
		needle: 5,
		expected: [4]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
		needle: 6,
		expected: [5]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
		needle: 7,
		expected: [6]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
		needle: 8,
		expected: [7]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
		needle: 9,
		expected: [8]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
		needle: 10,
		expected: [9]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
		needle: 11,
		expected: [10]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
		needle: 12,
		expected: [11]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
		needle: 13,
		expected: [12]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
		needle: 14,
		expected: [13]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
		needle: 15,
		expected: [14]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
		needle: 16,
		expected: [15]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
		needle: 17,
		expected: [16]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
		needle: 18,
		expected: [17]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
		needle: 19,
		expected: [18]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20],
		needle: 20,
		expected: [19]
	},
	// Length 21
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21],
		needle: 42,
		expected: [-1]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21],
		needle: 1,
		expected: [0]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21],
		needle: 2,
		expected: [1]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21],
		needle: 3,
		expected: [2]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21],
		needle: 4,
		expected: [3]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21],
		needle: 5,
		expected: [4]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21],
		needle: 6,
		expected: [5]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21],
		needle: 7,
		expected: [6]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21],
		needle: 8,
		expected: [7]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21],
		needle: 9,
		expected: [8]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21],
		needle: 10,
		expected: [9]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21],
		needle: 11,
		expected: [10]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21],
		needle: 12,
		expected: [11]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21],
		needle: 13,
		expected: [12]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21],
		needle: 14,
		expected: [13]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21],
		needle: 15,
		expected: [14]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21],
		needle: 16,
		expected: [15]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21],
		needle: 17,
		expected: [16]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21],
		needle: 18,
		expected: [17]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21],
		needle: 19,
		expected: [18]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21],
		needle: 20,
		expected: [19]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21],
		needle: 21,
		expected: [20]
	},
	{
		haystack: [1, 2, 3, 4, 5, 6, 6, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21],
		needle: 6,
		expected: [5, 6]
	},
];

const runTests = () => {
	let nbTests = 0;
	let failures = [];

	for (let testCase of testCases) {
		const actual = binSearch(testCase.haystack, testCase.needle);
		const passes = testCase.expected.includes(actual);
		nbTests++;
		if (!passes) {
			failures.push(testCase);
		}
		console.log(testCase, actual, passes ? 'ok' : 'FAIL');
	}

	console.log('------------------------');
	console.log(`Ran ${nbTests}, ${nbTests - failures.length} passed, ${failures.length} failed.`);
	console.log(failures);
};

runTests();