AlgorithmsJavascript

Binary search algorithm

Performs a binary search on the input array.

Here is the algorithm

/**
 * @param Array The array to search in
 * @param {*} needle : The item to search for within the array.
 * @return {Number} The index of the element which defaults to -1 when not found.
 */
function binaryIndexOf(arr, needle) {
   if (arr.length === 0) {
      return -1;
   }
   var minIndex = 0;
   var maxIndex = arr.length - 1;
   var currentIndex;
   var currentElement;

   while (minIndex <= maxIndex) {
      currentIndex = Math.floor((minIndex + maxIndex) / 2);
      currentElement = arr[currentIndex];

      if (currentElement < needle) {
         minIndex = currentIndex + 1;
      } else if (currentElement > needle) {
         maxIndex = currentIndex - 1;
      } else {
         return currentIndex;
      }
   }

   return -1;
}

ref: http://oli.me.uk/2013/06/08/searching-javascript-arrays-with-a-binary-search/