Created
September 29, 2013 18:19
-
-
Save toboqus/6755104 to your computer and use it in GitHub Desktop.
Binary searching through an array
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
Array.prototype.binarySearch = function(find, comparator) { | |
var low = 0, high = this.length - 1, | |
i, comparison; | |
while (low <= high) { | |
i = Math.floor((low + high) / 2); | |
comparison = comparator(this[i], find); | |
if (comparison < 0) { low = i + 1; continue; }; | |
if (comparison > 0) { high = i - 1; continue; }; | |
return i; | |
} | |
return null; | |
}; | |
//USAGE-------------------------------------------------------- | |
//searchValue is the value you want to find in the sorted array | |
//Array1 is the array you want to search through | |
//below will return the position in the array the search first finds a value for | |
Array1.binarySearch(searchValue, function (search, value) { | |
if (search < value) { | |
return -1 | |
} else if (search > value) { | |
return 1 | |
} else { | |
return 0; | |
} | |
}) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment