Last active
February 13, 2018 10:41
-
-
Save branneman/aaf9ed2b7c0944ad76141e114b4db7a8 to your computer and use it in GitHub Desktop.
JavaScript: Recursive Binary Search algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
const indexOf = node => list => { | |
const guess = (min, max) => { | |
const index = Math.floor((max - min) / 2) + min | |
if (list[index] === node) { | |
return index | |
} else if (list[index] < node) { | |
min = index + 1 | |
} else { | |
max = index - 1 | |
} | |
console.log(`Guessed wrong with ${list[index]}`) | |
return guess(min, max) | |
} | |
return guess(0, list.length - 1) | |
} | |
const primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173] | |
const query = 127 | |
console.log(`Using list of the first ${primes.length} primes`) | |
console.log(`Guessed right! ${query} is prime number ${indexOf(query)(primes) + 1}`) |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
$ node alg-binarysearch.js | |
Using list of the first 40 primes | |
Guessed wrong with 71 | |
Guessed wrong with 113 | |
Guessed wrong with 149 | |
Guessed wrong with 131 | |
Guessed right! 127 is prime number 31 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment