Skip to content

Instantly share code, notes, and snippets.

@Olical
Last active October 18, 2020 15:16
Show Gist options
  • Save Olical/5734530 to your computer and use it in GitHub Desktop.
Save Olical/5734530 to your computer and use it in GitHub Desktop.
JavaScript binary search with the same API as indexOf. Performance: http://jsperf.com/binaryindexof-and-indexof
/**
* Performs a binary search on the host array. This method can either be
* injected into Array.prototype or called with a specified scope like this:
* binaryIndexOf.call(someArray, searchElement);
*
* @param {*} searchElement The item to search for within the array.
* @return {Number} The index of the element which defaults to -1 when not found.
*/
function binaryIndexOf(searchElement) {
'use strict';
var minIndex = 0;
var maxIndex = this.length - 1;
var currentIndex;
var currentElement;
while (minIndex <= maxIndex) {
currentIndex = (minIndex + maxIndex) / 2 | 0;
currentElement = this[currentIndex];
if (currentElement < searchElement) {
minIndex = currentIndex + 1;
}
else if (currentElement > searchElement) {
maxIndex = currentIndex - 1;
}
else {
return currentIndex;
}
}
return -1;
}
/**
* Performs a binary search on the host array. This method can either be
* injected into Array.prototype or called with a specified scope like this:
* binaryIndexOf.call(someArray, searchElement);
*
* @param {*} e The item to search for within the array.
* @return {Number} The index of the element which defaults to -1 when not found.
*/
function s(e){for(var b=0,c=this.length-1,a,d;b<=c;)if(a=(b+c)/2|0,d=this[a],d<e)b=a+1;else if(d>e)c=a-1;else return a;return-1};
@zhuangya
Copy link

zhuangya commented Feb 5, 2015

@ftorre104 for some case that (mixIndex + maxIndex) becomes into NaN:

> NaN
NaN
> NaN / 2
NaN
> NaN / 2 | 0
0

just encure currentIndex is a number.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment