Last active
September 7, 2017 02:15
-
-
Save death667b/abe7c979ae445e1bd271e3cba15c0201 to your computer and use it in GitHub Desktop.
find a number in range - log n problem
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
function findNumber(minN, maxN, findMe, opNum = 0) { | |
// O(log n) | |
// if inital maxN is ... then there will be ... operations | |
// 100 ~6 ops | |
// 1,000 ~9 ops | |
// 10,000 ~13 ops | |
// 100,000 ~16 ops | |
// 100,000,000 ~26 ops | |
// 100,000,000,000 ~36 ops | |
// 100,000,000,000,000 ~46 ops | |
// Don't expect it to ever do more than 100 ops | |
// Here to both stop wasting time and prevent stack overflow | |
if (opNum > 100) return 'Maxed Out'; | |
testNumber = Math.round((maxN - minN) / 2) + minN; | |
console.log('Operation Number: ', opNum, ' testNumber: ', testNumber, ' min: ', minN, ' max: ', maxN); | |
if (findMe > testNumber) { | |
findNumber(testNumber, maxN, findMe, ++opNum); | |
} else if (findMe < testNumber) { | |
findNumber(minN, testNumber, findMe, ++opNum); | |
} | |
return testNumber; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Theoretically should eliminate the risk of a stack overflow as it means the recursion is handled by the event loop not the call stack. This only is practical in limited implementations though.