/**
 * Insert elements into sorted array using binary search to indentify correct index
 * @module lib/index
 */

module.exports = binarySearchInsert

/**
 * @param {Array} sortedArray
 * @param {*} item
 * @param {Function} comparator
 * @return {Array}
 */
function binarySearchInsert (sortedArray, item, comparator) {
  var low = 0;
  var high = sortedArray.length - 1;
  var lastIndex = high;

  if (high === -1) {
    sortedArray.push(item);
    return sortedArray;
  }

  while (low <= high) {
    // https://github.com/darkskyapp/binary-search
    // http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
    let mid = low + (high - low >> 1);
    let cmp = comparator(sortedArray[mid], item);
    if (cmp < 0.0) {
      // searching too low
      if (mid + 1 > lastIndex) {
        // place item at end of array
        sortedArray.push(item);
        return sortedArray;
      }

      let cmp2 = comparator(sortedArray[mid + 1], item);
      if (cmp2 >= 0.0) {
        // right item is too high or equal, insert in item to right of mid
        sortedArray.splice(mid + 1, 0, item);
        return sortedArray;
      }

      low = mid + 1;
    } else if (cmp > 0.0) {
      // searching too high
      if (mid === 0) {
        // place item at beginning of array
        sortedArray.splice(0, 0, item);
        return sortedArray;
      }

      let cmp2 = comparator(sortedArray[mid - 1], item);
      if (cmp2 <= 0.0) {
        // left item is too low or equal, insert in item to left of mid
        sortedArray.splice(mid - 1, 0, item);
        return sortedArray;
      }

      high = mid - 1;
    } else {
      // mid equals item
      sortedArray.splice(mid, 0, item);
      return sortedArray;
    }
  }
}

@@ -455,25 +455,216 @@
 urn 
-sortedArray;%0A  %7D%0A
+0;%0A  %7D%0A%0A  if (high === 0) %7B%0A    let cmp = comparator(sortedArray%5B0%5D, item);%0A    if (cmp %3C 0.0) %7B%0A      sortedArray.push(item);%0A    %7D else %7B%0A      sortedArray.unshift(item);%0A    %7D%0A    return 0;%0A  %7D%0A%0A  var mid;
 %0A  w
@@ -831,20 +831,16 @@
 tml%0A    
-let 
 mid = lo
@@ -917,32 +917,33 @@
 );%0A    if (cmp %3C
+=
  0.0) %7B%0A      //
@@ -965,388 +965,8 @@
 low%0A
-      if (mid + 1 %3E lastIndex) %7B%0A        // place item at end of array%0A        sortedArray.push(item);%0A        return sortedArray;%0A      %7D%0A%0A      let cmp2 = comparator(sortedArray%5Bmid + 1%5D, item);%0A      if (cmp2 %3E= 0.0) %7B%0A        // right item is too high or equal, insert in item to right of mid%0A        sortedArray.splice(mid + 1, 0, item);%0A        return sortedArray;%0A      %7D%0A%0A
     
@@ -996,23 +996,8 @@
 else
- if (cmp %3E 0.0)
  %7B%0A 
@@ -1033,447 +1033,35 @@
     
-if (mid === 0) %7B%0A        // place item at beginning of array%0A        sortedArray.splice(0, 0, item);%0A        return sortedArray;%0A      %7D%0A%0A      let cmp2 = comparator(sortedArray%5Bmid - 1%5D, item);%0A      if (cmp2 %3C= 0.0) %7B%0A        // left item is too low or equal, insert in item to left of mid%0A        sortedArray.splice(mid - 1, 0, item);%0A        return sortedArray;%0A      %7D%0A%0A      high = mid - 1;%0A    %7D else %7B%0A      // mid equals item%0A    
+high = mid - 1;%0A    %7D%0A  %7D%0A%0A
   so
@@ -1090,22 +1090,17 @@
 0, item)
-;
 %0A
-    
   return
@@ -1104,29 +1104,11 @@
 urn 
-sortedArray;%0A    %7D%0A  %7D
+mid;
 %0A%7D%0A

Remove unnecessary adjacent item comparisons