Skip to content

Instantly share code, notes, and snippets.

@branneman
Last active February 13, 2018 10:41
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save branneman/aaf9ed2b7c0944ad76141e114b4db7a8 to your computer and use it in GitHub Desktop.
Save branneman/aaf9ed2b7c0944ad76141e114b4db7a8 to your computer and use it in GitHub Desktop.
JavaScript: Recursive Binary Search algorithm
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}`)
$ 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