Skip to content

Instantly share code, notes, and snippets.

@LeopoldTal

LeopoldTal/binary-search.js

Created June 24, 2020 19:08
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save LeopoldTal/9713aecf4abb45c8515c95b913b017ab to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save LeopoldTal/9713aecf4abb45c8515c95b913b017ab to your computer and use it in GitHub Desktop.
Download ZIP
Cleanroom binary search challenge
Raw
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();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment