CODEWITHSUNDEEP
javascriptbinary-search
4m1r
4m1r

Reputation: 12542

Binary Search in Javascript

I'm trying to implement a binary search algorithm in JavaScript. Things seem okay, but my return statements appear to be returning undefined. Can anybody tell me what's wrong here?

Fiddle: http://jsfiddle.net/2mBdL/

var a = [
    1,
    2,
    4,
    6,
    1,
    100,
    0,
    10000,
    3
];

a.sort(function (a, b) {
    return a - b;
});

console.log('a,', a);

function binarySearch(arr, i) {
    var mid = Math.floor(arr.length / 2);
    console.log(arr[mid], i);
    
    if (arr[mid] === i) {
        console.log('match', arr[mid], i);
        return arr[mid];
    } else if (arr[mid] < i && arr.length > 1) {
        console.log('mid lower', arr[mid], i);
        binarySearch(arr.splice(mid, Number.MAX_VALUE), i);
    } else if (arr[mid] > i && arr.length > 1) {
        console.log('mid higher', arr[mid], i);
        binarySearch(arr.splice(0, mid), i);
    } else {
        console.log('not here', i);
        return -1;
    }
    
}
var result = binarySearch(a, 100);
console.log(result);

Upvotes: 81

Views: 156580

Answers (29)

Lior Elrom
Lior Elrom

Reputation: 20862

Binary Search (ES6)

These functions return the element's position (index) within a sorted array if it was found or -1 if it wasn't.

Bottom-up

function binarySearch(arr, val) {
  let start = 0;
  let end = arr.length - 1;

  while (start <= end) {
    let mid = Math.floor((start + end) / 2);

    if (arr[mid] === val) {
      return mid;
    }

    if (val < arr[mid]) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }
  return -1;
}

const arr = [0,1,2,3,4,6,100,10000];

console.log(binarySearch(arr, 100)); // 6

Recursive

function binarySearch(arr, val, start = 0, end = arr.length - 1) {
  const mid = Math.floor((start + end) / 2);

  if (val === arr[mid]) {
    return mid;
  }

  if (start >= end) {
    return -1;
  }

  return val < arr[mid]
    ? binarySearch(arr, val, start, mid - 1)
    : binarySearch(arr, val, mid + 1, end);
}

const arr = [0,1,2,3,4,6,100,10000];

console.log(binarySearch(arr, 1000)); // -1

Upvotes: 55

Friedrich -- Слава Україні
Friedrich -- Слава Україні

Reputation: 3734

Instead of binary search you may simply consider a linear search with findIndex (or findLastIndex or find or findLast). Likely slower for large array, but less coding...

var a = [0, 1, 1, 2, 3, 4, 6, 100, 10000];

i = a.findIndex(x => x >= 4)

console.log(`a[${i}] = ${a[i]}`)

Of course the array must be sorted.

Upvotes: 0

Alexander Ryzhov
Alexander Ryzhov

Reputation: 2920

It's useful to write a search function in such a way that it returns a negative value indicating the insertion point for the new element if the element is not found. Also, using recursion in a binary search is excessive and unnecessary. And finally, it's a good practice to make the search algorithm generic by supplying a comparator function as a parameter. Below is the implementation.

function binarySearch(arr, el, compare_fn) {
    let m = 0;
    let n = arr.length - 1;
    while (m <= n) {
        let k = (n + m) >> 1;
        let cmp = compare_fn(el, arr[k]);
        if (cmp > 0) {
            m = k + 1;
        } else if(cmp < 0) {
            n = k - 1;
        } else {
            return k;
        }
    }
    return ~m;
}

This code with comments and a unit test here.

Upvotes: 128

Jack G
Jack G

Reputation: 5322

𝗬𝗼𝘂 𝘄𝗮𝗻𝘁 𝘀𝗽𝗲𝗲𝗱? 𝗥𝗲𝗮𝗱 𝘁𝗵𝗶𝘀.

Binary searches implemented right (without modifying the array, making shallow copies of the array, or other absurdities) have an average complexity around O(k*log2(n)) (where k is constant representing needless overhead). Say you have an array of 1024 elements, and the constant k is 1 in this case. With a linear search, the average complexity would be O(k*n/2)=O(1*1024/2)=O(512). With a binary search, you would have a complexity of O(k*log2(n))=O(1*log2(1024))=O(1*10)=O(10). Now, say that you make both the linear search algorithm 25% faster and the binary search algorithm 25% faster. Now, k is 0.75 for both algorithms. The complexity of the linear search decreases to O(384) (a gain of 128 performance points), whereas the binary search decreases to O(7.5) (a gain of only 2.5 performance points). This minimal gain from optimizing the binary search method is because the binary search method is already so fast. Therefore, any sane person should be more inclined to optimize the rest of their program before they try to optimize their binary search algorithm. Despite this clear line of reasoning, I eventually gave into temptations and optimized the binary search function to the absolute limits of JavaScript engineering.

To start off the performance maxima, let us first investigate the initial function I started with. This function may be much slower than the ones shown further down the page (it's still much faster than any other answer posted here), but it should be much less confusing.

const sArr = [0,4,5,6,9,13,14,21,27,44];
const s = sArr[Math.random() * sArr.length | 0];
document.body.innerHTML = s+" is at "+compactBS(sArr, s);

function compactBS(array, searchedValue, ARG_start, ARG_len){
  // `void 0` is shorthand for `undefined`
  // Range of [start, start+len): only start is inclusive. It works
  // similarly to "...".substr(start, len).indexOf(sValue)
  // `void 0` is shorthand for `undefined`
  var start = ARG_start | 0;
  var len = ARG_len === void 0 ? array.length|0 : start+(ARG_len|0)|0;
  var offset = 0;

  for (var i=30; i >= 0; i=i-1|0) {
    offset = start + ((1<<i) - 1|0)|0;
    if (offset < len) {
      start = start + ((array[offset] < searchedValue) << i) | 0;
    }
  }

  if (array[start|0] !== searchedValue) {
    // remove this if-statement to return the next closest
    // element going downwards from the searched-for value
    // OR 0 if the value is less than all values in the
    // array. https://stackoverflow.com/a/44981570/5601591
    return -1 - start |0;
  }
  return start |0;
}

The return value of the above function is as follows.

  • If the value was found, then it returns the index of the value.
  • If the value was not found, then it returns -1 - nearestIndex where the nearestIndex is the index found which is the closest number <= index and capped at 0.
  • If the array is not sorted within the specified range, then it will return some meaningless number.

And now, then, unroll it, precompute it, make it fast, nice and good, just like that:

const sArr = [0,4,5,6,9,13,14,21,27,44];
const s = sArr[Math.random() * sArr.length | 0];
document.body.innerHTML = s+" is at index "+goodBinarySearch(sArr, s);

function goodBinarySearch(array, sValue, ARG_start, ARG_len) {
  // Range of [start, start+len): only start is inclusive. It works
  // similarly to "...".substr(start, len).indexOf(sValue)
  // `void 0` is shorthand for `undefined`
  var start = ARG_start | 0;
  var len = ARG_len === void 0 ? (array.length|0) - start |0 : ARG_len|0;
  var offset = 0;

  if ((offset = start + 0x3fffffff|0) < len) {
    start = start + ((array[offset] < sValue) << 30) | 0;
  }
  if ((offset = start + 0x1fffffff|0) < len) {
    start = start + ((array[offset] < sValue) << 29) | 0;
  }
  if ((offset = start + 0x0fffffff|0) < len) {
    start = start + ((array[offset] < sValue) << 28) | 0;
  }
  if ((offset = start + 0x07ffffff|0) < len) {
    start = start + ((array[offset] < sValue) << 27) | 0;
  }
  if ((offset = start + 0x03ffffff|0) < len) {
    start = start + ((array[offset] < sValue) << 26) | 0;
  }
  if ((offset = start + 0x01ffffff|0) < len) {
    start = start + ((array[offset] < sValue) << 25) | 0;
  }
  if ((offset = start + 0x00ffffff|0) < len) {
    start = start + ((array[offset] < sValue) << 24) | 0;
  }
  if ((offset = start + 0x007fffff|0) < len) {
    start = start + ((array[offset] < sValue) << 23) | 0;
  }
  if ((offset = start + 0x003fffff|0) < len) {
    start = start + ((array[offset] < sValue) << 22) | 0;
  }
  if ((offset = start + 0x001fffff|0) < len) {
    start = start + ((array[offset] < sValue) << 21) | 0;
  }
  if ((offset = start + 0x000fffff|0) < len) {
    start = start + ((array[offset] < sValue) << 20) | 0;
  }
  if ((offset = start + 0x0007ffff|0) < len) {
    start = start + ((array[offset] < sValue) << 19) | 0;
  }
  if ((offset = start + 0x0003ffff|0) < len) {
    start = start + ((array[offset] < sValue) << 18) | 0;
  }
  if ((offset = start + 0x0001ffff|0) < len) {
    start = start + ((array[offset] < sValue) << 17) | 0;
  }
  if ((offset = start + 0x0000ffff|0) < len) {
    start = start + ((array[offset] < sValue) << 16) | 0;
  }
  if ((offset = start + 0x00007fff|0) < len) {
    start = start + ((array[offset] < sValue) << 15) | 0;
  }
  if ((offset = start + 0x00003fff|0) < len) {
    start = start + ((array[offset] < sValue) << 14) | 0;
  }
  if ((offset = start + 0x00001fff|0) < len) {
    start = start + ((array[offset] < sValue) << 13) | 0;
  }
  if ((offset = start + 0x00000fff|0) < len) {
    start = start + ((array[offset] < sValue) << 12) | 0;
  }
  if ((offset = start + 0x000007ff|0) < len) {
    start = start + ((array[offset] < sValue) << 11) | 0;
  }
  if ((offset = start + 0x000003ff|0) < len) {
    start = start + ((array[offset] < sValue) << 10) | 0;
  }
  if ((offset = start + 0x000001ff|0) < len) {
    start = start + ((array[offset] < sValue) << 9) | 0;
  }
  if ((offset = start + 0x000000ff|0) < len) {
    start = start + ((array[offset] < sValue) << 8) | 0;
  }
  if ((offset = start + 0x0000007f|0) < len) {
    start = start + ((array[offset] < sValue) << 7) | 0;
  }
  if ((offset = start + 0x0000003f|0) < len) {
    start = start + ((array[offset] < sValue) << 6) | 0;
  }
  if ((offset = start + 0x0000001f|0) < len) {
    start = start + ((array[offset] < sValue) << 5) | 0;
  }
  if ((offset = start + 0x0000000f|0) < len) {
    start = start + ((array[offset] < sValue) << 4) | 0;
  }
  if ((offset = start + 0x00000007|0) < len) {
    start = start + ((array[offset] < sValue) << 3) | 0;
  }
  if ((offset = start + 0x00000003|0) < len) {
    start = start + ((array[offset] < sValue) << 2) | 0;
  }
  if ((offset = start + 0x00000001|0) < len) {
    start = start + ((array[offset] < sValue) << 1) | 0;
  }
  if (start < len) {
    start = start + ((array[start] < sValue) << 0) | 0;
  }

  if (array[start|0] !== sValue) {
    // remove this if-statement to return the next closest
    // element going downwards from the searched-for value
    // OR 0 if the value is less than all values in the
    // array. https://stackoverflow.com/a/44981570/5601591
    return -1 - start |0;
  }
  return start |0;
}

To further optimize performance, we can interleave the if-statements and use bitwise manipulations to make the last three checks branchless like so:

const sArr = [0,4,5,6,9,13,14,21,27,44];
const s = sArr[Math.random() * sArr.length | 0];
document.body.innerHTML = s+" is at index "+fastBinarySearch(sArr, s);

function fastBinarySearch(array, sValue, ARG_start, ARG_len) {
  // Range of [start, start+len): only start is inclusive. It works
  // similarly to "...".substr(start, len).indexOf(sValue)
  // `void 0` is shorthand for `undefined`
  var start = ARG_start | 0;
  var len = ARG_len === void 0 ? (array.length|0) - start |0 : ARG_len|0;
  var offset = 0, nCB = 0;

  if ((start + 0x00007fff|0) < len) {
    if ((start + 0x007fffff|0) < len) {
      if ((start + 0x07ffffff|0) < len) {
        if ((start + 0x1fffffff|0) < len) {
          if ((offset = start + 0x3fffffff|0) < len) {
            start = start + ((array[offset] < sValue) << 30) | 0;
          }
          if ((offset = start + 0x1fffffff|0) < len) {
            start = start + ((array[offset] < sValue) << 29) | 0;
          }
        }
        if ((offset = start + 0x0fffffff|0) < len) {
          start = start + ((array[offset] < sValue) << 28) | 0;
        }
        if ((offset = start + 0x07ffffff|0) < len) {
          start = start + ((array[offset] < sValue) << 27) | 0;
        }
      }
      if ((start + 0x01ffffff|0) < len) {
        if ((offset = start + 0x03ffffff|0) < len) {
          start = start + ((array[offset] < sValue) << 26) | 0;
        }
        if ((offset = start + 0x01ffffff|0) < len) {
          start = start + ((array[offset] < sValue) << 25) | 0;
        }
      }
      if ((offset = start + 0x00ffffff|0) < len) {
        start = start + ((array[offset] < sValue) << 24) | 0;
      }
      if ((offset = start + 0x007fffff|0) < len) {
        start = start + ((array[offset] < sValue) << 23) | 0;
      }
    }
    if ((start + 0x0007ffff|0) < len) {
      if ((start + 0x001fffff|0) < len) {
        if ((offset = start + 0x003fffff|0) < len) {
          start = start + ((array[offset] < sValue) << 22) | 0;
        }
        if ((offset = start + 0x001fffff|0) < len) {
          start = start + ((array[offset] < sValue) << 21) | 0;
        }
      }
      if ((offset = start + 0x000fffff|0) < len) {
        start = start + ((array[offset] < sValue) << 20) | 0;
      }
      if ((offset = start + 0x0007ffff|0) < len) {
        start = start + ((array[offset] < sValue) << 19) | 0;
      }
    }
    if ((start + 0x0001ffff|0) < len) {
      if ((offset = start + 0x0003ffff|0) < len) {
        start = start + ((array[offset] < sValue) << 18) | 0;
      }
      if ((offset = start + 0x0001ffff|0) < len) {
        start = start + ((array[offset] < sValue) << 17) | 0;
      }
    }
    if ((offset = start + 0x0000ffff|0) < len) {
      start = start + ((array[offset] < sValue) << 16) | 0;
    }
    if ((offset = start + 0x00007fff|0) < len) {
      start = start + ((array[offset] < sValue) << 15) | 0;
    }
  }
  if ((start + 0x0000007f|0) < len) {
    if ((start + 0x000007ff|0) < len) {
      if ((start + 0x00001fff|0) < len) {
        if ((offset = start + 0x00003fff|0) < len) {
          start = start + ((array[offset] < sValue) << 14) | 0;
        }
        if ((offset = start + 0x00001fff|0) < len) {
          start = start + ((array[offset] < sValue) << 13) | 0;
        }
      }
      if ((offset = start + 0x00000fff|0) < len) {
        start = start + ((array[offset] < sValue) << 12) | 0;
      }
      if ((offset = start + 0x000007ff|0) < len) {
        start = start + ((array[offset] < sValue) << 11) | 0;
      }
    }
    if ((start + 0x000001ff|0) < len) {
      if ((offset = start + 0x000003ff|0) < len) {
        start = start + ((array[offset] < sValue) << 10) | 0;
      }
      if ((offset = start + 0x000001ff|0) < len) {
        start = start + ((array[offset] < sValue) << 9) | 0;
      }
    }
    if ((offset = start + 0x000000ff|0) < len) {
      start = start + ((array[offset] < sValue) << 8) | 0;
    }
    if ((offset = start + 0x0000007f|0) < len) {
      start = start + ((array[offset] < sValue) << 7) | 0;
    }
  }
  if ((start + 0x00000007|0) < len) {
    if ((start + 0x0000001f|0) < len) {
      if ((offset = start + 0x0000003f|0) < len) {
        start = start + ((array[offset] < sValue) << 6) | 0;
      }
      if ((offset = start + 0x0000001f|0) < len) {
        start = start + ((array[offset] < sValue) << 5) | 0;
      }
    }
    if ((offset = start + 0x0000000f|0) < len) {
      start = start + ((array[offset] < sValue) << 4) | 0;
    }
    if ((offset = start + 0x00000007|0) < len) {
      start = start + ((array[offset] < sValue) << 3) | 0;
    }
  }

  offset = start + 0x00000003|0;
  nCB = -(offset < len|0) | 0;
  start = start + (((array[offset & nCB] < sValue) << 2) & nCB) | 0;

  offset = start + 0x00000001|0;
  nCB = -(offset < len|0) | 0;
  start = start + (((array[offset & nCB] < sValue) << 1) & nCB) | 0;

  offset = start;
  nCB = -(offset < len|0) | 0;
  start = start + ((array[offset & nCB] < sValue) & nCB) | 0;

  if (array[start|0] !== sValue) {
    // remove this if-statement to return the next closest
    // element going downwards from the searched-for value
    // OR 0 if the value is less than all values in the
    // array. https://stackoverflow.com/a/44981570/5601591
    return -1 - start |0;
  }
  
  return start |0;
}

But wait... asunder whispers the eve of even greater performance. Likely, you are calling the binary search in a tight loop. In such a case, we can precompute the first value that will actually get processed and skip right to it with a high performance integer index switch statement. HOWEVER, while using this, you must make certain that you never reuse the generated fast function after the length of the array has been modified because then only part of the array will be searched.

const clz32 = Math.clz32 || (function(log, LN2){
  return function(x) {
    return 31 - log(x >>> 0) / LN2 | 0; // the "| 0" acts like math.floor
  };
})(Math.log, Math.LN2);
const ArrayProtoSlice = Array.prototype.slice;

const sArr = [0,4,5,6,9,13,14,21,27,44];
const compFunc = fastestBS(sArr);
for (var i=0,str="",len=sArr.length|0; i < len; i=i+1|0)
  str += sArr[i]+" is at "+compFunc(sArr[i])+"<br/>";
document.body.innerHTML = str; // show the result

function fastestBS(array, ARG_start, ARG_len){
  // Range of [start, start+len): only start is inclusive. It works
  // similarly to "...".substr(start, len).indexOf(sValue)
  // `void 0` is shorthand for `undefined`
  var init_start = ARG_start | 0;
  var len = ARG_len === void 0 ? array.length|0 : init_start+(ARG_len|0)|0;
  const compGoto = clz32(len) & 31;

  var arrPadded = array;
  var relLen = len - init_start | 0;
  if (relLen & (relLen - 1)) { // if its not a power of 2
    var sizeUp = relLen;
    sizeUp |= sizeUp >>> 16;
    sizeUp |= sizeUp >>> 8;
    sizeUp |= sizeUp >>> 4;
    sizeUp |= sizeUp >>> 2;
    sizeUp |= sizeUp >>> 1;
    sizeUp = sizeUp + 1 - relLen | 0;

    arrPadded = ArrayProtoSlice.call(array);

    var accCur = [array[len - 1 | 0]];
    while (1 < sizeUp && accCur.length < 65536) {
      if (sizeUp & 1) arrPadded.push.apply(arrPadded, accCur);
      sizeUp >>>= 1;
      accCur.push.apply(accCur, accCur);
    }
    for (var i=0; i < sizeUp; i=i+1|0) {
      arrPadded.push.apply(arrPadded, accCur);
    }
  }

  return function(sValue) {
    var start = init_start | 0, offset = 0;
    switch (compGoto) {
      case 1:
        start = start + ((arrPadded[start + 0x3fffffff|0] < sValue) << 30) | 0;
      case 2:
        start = start + ((arrPadded[start + 0x1fffffff|0] < sValue) << 29) | 0;
      case 3:
        start = start + ((arrPadded[start + 0x0fffffff|0] < sValue) << 28) | 0;
      case 4:
        start = start + ((arrPadded[start + 0x07ffffff|0] < sValue) << 27) | 0;
      case 5:
        start = start + ((arrPadded[start + 0x03ffffff|0] < sValue) << 26) | 0;
      case 6:
        start = start + ((arrPadded[start + 0x01ffffff|0] < sValue) << 25) | 0;
      case 7:
        start = start + ((arrPadded[start + 0x00ffffff|0] < sValue) << 24) | 0;
      case 8:
        start = start + ((arrPadded[start + 0x007fffff|0] < sValue) << 23) | 0;
      case 9:
        start = start + ((arrPadded[start + 0x003fffff|0] < sValue) << 22) | 0;
      case 10:
        start = start + ((arrPadded[start + 0x001fffff|0] < sValue) << 21) | 0;
      case 11:
        start = start + ((arrPadded[start + 0x000fffff|0] < sValue) << 20) | 0;
      case 12:
        start = start + ((arrPadded[start + 0x0007ffff|0] < sValue) << 19) | 0;
      case 13:
        start = start + ((arrPadded[start + 0x0003ffff|0] < sValue) << 18) | 0;
      case 14:
        start = start + ((arrPadded[start + 0x0001ffff|0] < sValue) << 17) | 0;
      case 15:
        start = start + ((arrPadded[start + 0x0000ffff|0] < sValue) << 16) | 0;
      case 16:
        start = start + ((arrPadded[start + 0x00007fff|0] < sValue) << 15) | 0;
      case 17:
        start = start + ((arrPadded[start + 0x00003fff|0] < sValue) << 14) | 0;
      case 18:
        start = start + ((arrPadded[start + 0x00001fff|0] < sValue) << 13) | 0;
      case 19:
        start = start + ((arrPadded[start + 0x00000fff|0] < sValue) << 12) | 0;
      case 20:
        start = start + ((arrPadded[start + 0x000007ff|0] < sValue) << 11) | 0;
      case 21:
        start = start + ((arrPadded[start + 0x000003ff|0] < sValue) << 10) | 0;
      case 22:
        start = start + ((arrPadded[start + 0x000001ff|0] < sValue) << 9) | 0;
      case 23:
        start = start + ((arrPadded[start + 0x000000ff|0] < sValue) << 8) | 0;
      case 24:
        start = start + ((arrPadded[start + 0x0000007f|0] < sValue) << 7) | 0;
      case 25:
        start = start + ((arrPadded[start + 0x0000003f|0] < sValue) << 6) | 0;
      case 26:
        start = start + ((arrPadded[start + 0x0000001f|0] < sValue) << 5) | 0;
      case 27:
        start = start + ((arrPadded[start + 0x0000000f|0] < sValue) << 4) | 0;
      case 28:
        start = start + ((arrPadded[start + 0x00000007|0] < sValue) << 3) | 0;
      case 29:
        start = start + ((arrPadded[start + 0x00000003|0] < sValue) << 2) | 0;
      case 30:
        start = start + ((arrPadded[start + 0x00000001|0] < sValue) << 1) | 0;
      case 31:
        start = start + ((arrPadded[start] < sValue) << 0) | 0;
    }
    if (arrPadded[start|0] !== sValue) {
      if (len <= start) start = len - 1 | 0; // because we padd the array up to the next power of 2
      // remove this if-statement to return the next closest
      // element going downwards from the searched-for value
      // OR 0 if the value is less than all values in the
      // array. https://stackoverflow.com/a/44981570/5601591
      return -1 - start |0;
    }
    return start;
  };
}

Demo:

(function(document){"use strict";
var textarea = document.getElementById('inputbox'),
    searchinput = document.getElementById('search'),
    searchStart = document.getElementById('start'),
    searchedLength = document.getElementById('length'),
    resultbox = document.getElementById('result'),
    timeoutID = -1;
function doUpdate(){
   try {
      var txt = textarea.value.replace(/\s*\[|\]\s*/g, '').split(',');
      var arr = JSON.parse(textarea.value);
      var searchval = JSON.parse(searchinput.value);
      var textmtchs = textarea.value.match(/\s*\[|\]\s*/g);
      var start = searchStart.value || void 0;
      var sub = searchedLength.value || void 0;
      
      txt = refSort(txt, arr);
      textarea.value = textmtchs[0] +
                        txt.join(',') +
                       textmtchs[textmtchs.length-1];
      arr = JSON.parse(textarea.value);
      resultbox.value = fastBinarySearch(arr, searchval, start, sub);
   } catch(e) {
      resultbox.value = 'Error';
   }
}
textarea.oninput = searchinput.oninput = 
    searchStart.oninput = searchedLength.oninput =
    textarea.onkeyup = searchinput.onkeyup = 
    searchStart.onkeyup = searchedLength.onkeyup = 
    textarea.onchange = searchinput.onchange = 
    searchStart.onchange = searchedLength.onchange = function(e){
  clearTimeout( timeoutID );
  timeoutID = setTimeout(doUpdate, e.target === textarea ? 384 : 125);
}

function refSort(targetData, refData) {
  var indices = Object.keys(refData);
  indices.sort(function(indexA, indexB) {
    if (refData[indexA] < refData[indexB]) return -1;
    if (refData[indexA] > refData[indexB]) return 1;
    return 0;
  });
  return indices.map(function(i){ return targetData[i] })
}
function fastBinarySearch(array, sValue, ARG_start, ARG_len) {
  // Range of [start, start+len): only start is inclusive. It works
  // similarly to "...".substr(start, len).indexOf(sValue)
  // `void 0` is shorthand for `undefined`
  var start = ARG_start | 0;
  var len = ARG_len === void 0 ? (array.length|0) - start |0 : ARG_len|0;
  var offset = 0, nCB = 0;

  if ((start + 0x00007fff|0) < len) {
    if ((start + 0x007fffff|0) < len) {
      if ((start + 0x07ffffff|0) < len) {
        if ((start + 0x1fffffff|0) < len) {
          if ((offset = start + 0x3fffffff|0) < len) {
            start = start + ((array[offset] < sValue) << 30) | 0;
          }
          if ((offset = start + 0x1fffffff|0) < len) {
            start = start + ((array[offset] < sValue) << 29) | 0;
          }
        }
        if ((offset = start + 0x0fffffff|0) < len) {
          start = start + ((array[offset] < sValue) << 28) | 0;
        }
        if ((offset = start + 0x07ffffff|0) < len) {
          start = start + ((array[offset] < sValue) << 27) | 0;
        }
      }
      if ((start + 0x01ffffff|0) < len) {
        if ((offset = start + 0x03ffffff|0) < len) {
          start = start + ((array[offset] < sValue) << 26) | 0;
        }
        if ((offset = start + 0x01ffffff|0) < len) {
          start = start + ((array[offset] < sValue) << 25) | 0;
        }
      }
      if ((offset = start + 0x00ffffff|0) < len) {
        start = start + ((array[offset] < sValue) << 24) | 0;
      }
      if ((offset = start + 0x007fffff|0) < len) {
        start = start + ((array[offset] < sValue) << 23) | 0;
      }
    }
    if ((start + 0x0007ffff|0) < len) {
      if ((start + 0x001fffff|0) < len) {
        if ((offset = start + 0x003fffff|0) < len) {
          start = start + ((array[offset] < sValue) << 22) | 0;
        }
        if ((offset = start + 0x001fffff|0) < len) {
          start = start + ((array[offset] < sValue) << 21) | 0;
        }
      }
      if ((offset = start + 0x000fffff|0) < len) {
        start = start + ((array[offset] < sValue) << 20) | 0;
      }
      if ((offset = start + 0x0007ffff|0) < len) {
        start = start + ((array[offset] < sValue) << 19) | 0;
      }
    }
    if ((start + 0x0001ffff|0) < len) {
      if ((offset = start + 0x0003ffff|0) < len) {
        start = start + ((array[offset] < sValue) << 18) | 0;
      }
      if ((offset = start + 0x0001ffff|0) < len) {
        start = start + ((array[offset] < sValue) << 17) | 0;
      }
    }
    if ((offset = start + 0x0000ffff|0) < len) {
      start = start + ((array[offset] < sValue) << 16) | 0;
    }
    if ((offset = start + 0x00007fff|0) < len) {
      start = start + ((array[offset] < sValue) << 15) | 0;
    }
  }
  if ((start + 0x0000007f|0) < len) {
    if ((start + 0x000007ff|0) < len) {
      if ((start + 0x00001fff|0) < len) {
        if ((offset = start + 0x00003fff|0) < len) {
          start = start + ((array[offset] < sValue) << 14) | 0;
        }
        if ((offset = start + 0x00001fff|0) < len) {
          start = start + ((array[offset] < sValue) << 13) | 0;
        }
      }
      if ((offset = start + 0x00000fff|0) < len) {
        start = start + ((array[offset] < sValue) << 12) | 0;
      }
      if ((offset = start + 0x000007ff|0) < len) {
        start = start + ((array[offset] < sValue) << 11) | 0;
      }
    }
    if ((start + 0x000001ff|0) < len) {
      if ((offset = start + 0x000003ff|0) < len) {
        start = start + ((array[offset] < sValue) << 10) | 0;
      }
      if ((offset = start + 0x000001ff|0) < len) {
        start = start + ((array[offset] < sValue) << 9) | 0;
      }
    }
    if ((offset = start + 0x000000ff|0) < len) {
      start = start + ((array[offset] < sValue) << 8) | 0;
    }
    if ((offset = start + 0x0000007f|0) < len) {
      start = start + ((array[offset] < sValue) << 7) | 0;
    }
  }
  if ((start + 0x00000007|0) < len) {
    if ((start + 0x0000001f|0) < len) {
      if ((offset = start + 0x0000003f|0) < len) {
        start = start + ((array[offset] < sValue) << 6) | 0;
      }
      if ((offset = start + 0x0000001f|0) < len) {
        start = start + ((array[offset] < sValue) << 5) | 0;
      }
    }
    if ((offset = start + 0x0000000f|0) < len) {
      start = start + ((array[offset] < sValue) << 4) | 0;
    }
    if ((offset = start + 0x00000007|0) < len) {
      start = start + ((array[offset] < sValue) << 3) | 0;
    }
  }

  offset = start + 0x00000003|0;
  nCB = -(offset < len|0) | 0;
  start = start + (((array[offset & nCB] < sValue) << 2) & nCB) | 0;

  offset = start + 0x00000001|0;
  nCB = -(offset < len|0) | 0;
  start = start + (((array[offset & nCB] < sValue) << 1) & nCB) | 0;

  offset = start;
  nCB = -(offset < len|0) | 0;
  start = start + ((array[offset & nCB] < sValue) & nCB) | 0;

  if (array[start|0] !== sValue) {
    // remove this if-statement to return the next closest
    // element going downwards from the searched-for value
    // OR 0 if the value is less than all values in the
    // array. https://stackoverflow.com/a/44981570/5601591
    return -1 - start |0;
  }
  
  return start |0;
}
})(document);
<h3 style="margin:.125em;width:100%;text-align:center">The Array (Must Be A Valid JSON Array)</h3>
<textarea placeholder="[-24, -12, 0, 0, 9, 16, 18, 64, 80]" type="text" rows=6 style="width:calc(100% - .5em);display:block" id="inputbox">[-24, -12, 0, 0, 9, 16, 18, 64, 80]</textarea>

<table style="table-layout:fixed;font-size:1.2em" width="100%"><tbody>
  <tr>
    <td colspan="3">Search Value: <input type="text" id="search" value="-12" style="width:8em;text-align:center;float:right" /></td>
    <td></td>
    <td colspan="3">Resulting Index: <input type="text" id="result" value="1" style="width:8em;text-align:center;float:right" readonly="" />
  </tr>
  <tr>
    <td colspan="3">Start Index: <input type="text" id="start" value="" placeholder="(0)" style="width:8em;text-align:center;float:right" /></td>
    <td></td>
    <td colspan="3">Searched Length: <input type="text" id="length" value="" placeholder="(array length)" style="width:8em;text-align:center;float:right" />
  </tr>
</tbody></table>

You can also use an array of strings (surrounded by quotation marks) in the demo, and it should work just fine. To search for a string, you must put quotes around the search value.

Upvotes: 25

vijaykumar Mahendran
vijaykumar Mahendran

Reputation: 37

const SearchArray =(Listarr, Key)=>{
  
  const midvalues = Math.floor(Listarr.length/2)
 
  if(Key===Listarr[midvalues]) return true
  
  else if(Listarr[midvalues]<=Key && midvalues>0 )
    return SearchArray(Listarr.slice(midvalues,Listarr.length), Key)
  
  else if(Listarr[midvalues]>=Key && midvalues>0 )
    return SearchArray(Listarr.slice(0, midvalues) , Key)
  else
    return "No record found"
  
  
}
const arr = [11,24,26,37,40,43,56,75,87];

console.log(SearchArray(arr, 75))
console.log(SearchArray(arr, 87))
console.log(SearchArray(arr, 11))
console.log(SearchArray(arr, 26))

Upvotes: 0

rofrol
rofrol

Reputation: 15226

Port of zig's binarySearch:

  • Uses < instead of <= so one less comparison
  • Above allows to use unsigned int for right - for languages like zig or rust
  • Computes middle without overflowing mid - for languages like zig or rust
const binarySearch = (key, items, compareFn) => {
  let left = 0;
  let right = items.length;
  while (left < right) {
    const mid = left + Math.floor((right - left) / 2);
    const cmp = compareFn(key, items[mid]);
    if (cmp === 0) return mid;
    if (cmp < 0) right = mid;
    else left = mid + 1;

    // happens when right = items.length - 1 and key = 2 and items = [3]
    if (right < 0) throw new Error("right is < 0");
  }
  return -1;
};

const compareFn = (a, b) => a - b;
console.log(binarySearch(33, new Int16Array([1, 3, 4, 2, 33, 20, 10, 12, 34]).sort(), compareFn));
console.log(binarySearch(2, new Int16Array([3]).sort(), compareFn));

Upvotes: 0

copremesis
copremesis

Reputation: 776

no mutations and recursive

let A = [ ...Array(100).keys() ].map((x) => Math.floor(Math.random() * 1000)).sort((a,b) => a-b)
const binarySearch = (A, a, b, k) => {
  const m = Math.floor((b + a)/ 2);
  console.log(a, m, b, k)
  if(A[m] === k) { 
    return m; 
  }

  if(A[a] <= k && k <= A[m]) { 
    return binarySearch(A, a,   m, k) 
  }

  if(A[m] <  k && k <= A[b]) { 
    return binarySearch(A, m+1, b, k) 
  }

  return -1;
}
console.log(`key ${A[30]}`);
rez = binarySearch(A, 0, 100, A[30])
console.log(`rez is ${rez} and index of ${A[30]} is ${A.indexOf(A[30])}`);

rez = binarySearch(A, 0, 100, 666)
console.log(`rez is ${rez} and index of ${666} is ${A.indexOf(666)}`);

Upvotes: 0

Eduard
Eduard

Reputation: 2138

Did a bit differently. Take a look

function binarySearch(arr, n) {
  let min = 0;
  let max = arr.length - 1;
  let mid;
  while (min <= max) {
    mid = (min + max) >>> 1;
    if (arr[mid] === n) {
      return mid;
    } else if (arr[mid] < n) {
      min = mid + 1;
    } else {
      max = mid - 1;
    }
  }

  return -1;
}

binarySearch([1,2,3,5,56], 2);

Upvotes: 5

WesleyAC
WesleyAC

Reputation: 553

A lot of overly complicated answers here! You want to return the index if the value is found; otherwise return the negative of the index where the value would have been, if it had been in the array. You also want it to be generic enough to handle linguistic expressions in addition to numbers:

function BinarySearch(array, value) {
    let high = array.length - 1;
    let low = 0;

    if (value < array[low]) 
        return -1;
    if (value > array[high]) 
        return -(high + 1);

    while (high >= low) {
        var mid = (high + low) >> 1;

        if (value === array[mid])
            return mid;
        else if (value < array[mid])
            high = mid - 1;
        else
            low = mid + 1;
    }

    return -(mid + 1);
}

var c = ['alpha','apple','beta','delta','gamma','zebra'];
console.log(BinarySearch(c,'delta')); // return 3
console.log(BinarySearch(c,'beet')); // return -2
var a = [1,2,3,4,6,7,8,9,10];
var b = [1,2,3,4,5,6,7,8,9,10];
console.log(BinarySearch(a,5)); // return -4
console.log(BinarySearch(a,11)); // return -9
console.log(BinarySearch(b,5)); // return 4
console.log(BinarySearch(b,0)); // return -1

Or, if you just want to return true if found and false otherwise:

function BinarySearch(array, value) {
    let high = array.length - 1;
    let low = 0;

    if (value < array[low] || value > array[high]) 
        return false;

    while (high >= low) {
        let mid = (high + low) >> 1;

        if (value === array[mid])
            return true;
        else if (value < array[mid])
            high = mid - 1;
        else
            low = mid + 1;
    }

    return false;
}

Upvotes: 1

Avadhut Thorat
Avadhut Thorat

Reputation: 1195

Here we go.

let a = [1, 2, 4, 6, 1, 100, 0, 10000, 3];

a.sort(function (a, b) {
    return a - b;
});

function binarySearch(arr,value){
        if(arr.length === 0) return -1;
        var low  = 0 , high = arr.length -1 ,mid ;      
        while (low <= high){
            mid = Math.floor((low+high)/2);     
            if(arr[mid]==value) return mid ; 
            else if (arr[mid]<value) low = mid+1;
            else high = mid-1;          
        }
        return -1 ;
}
console.log(binarySearch(a,1005))

Here is the working fiddle - https://jsfiddle.net/avadhutthorat/6Lq1r582/

Upvotes: -1

Purkhalo Alex
Purkhalo Alex

Reputation: 3627

Recursively divides the searching range by half until reaching the appropriate value or overshooting the searching range:

const binarySearch = (arr, item, [low=0, high=arr.length-1]=[]) => {
  const mid = Math.floor((low + high)/2)

  if (low > high) return -1 // is overshooting the range?
  if (arr[mid] === item) return mid // is item found?

  return binarySearch(arr, item, [
    item > arr[mid] ? mid+1 : low,
    item < arr[mid] ? mid-1 : high
  ])
}

Let's test it:

// positive
console.log(binarySearch([2, 6, 9, 14, 21],  9)) // => 2
console.log(binarySearch([2, 6, 9, 14, 21], 21)) // => 4
console.log(binarySearch([2, 6, 9, 14, 21],  2)) // => 0

// negative
console.log(binarySearch([2, 6, 9, 14, 21],  0)) // => -1
console.log(binarySearch([2, 6, 9, 14, 21], -4)) // => -1
console.log(binarySearch([2, 6, 9, 14, 21], 40)) // => -1

Upvotes: 0

Manoj Reddy Mettu
Manoj Reddy Mettu

Reputation: 139

Posting the answer if in case someone wants

  1. Recursive and non-recursive way
  2. With comments straight away

Recursive way

/**
 * Binary Search - With recursive
 * @param arr - Input Array
 * @param searchElement - Element to search
 * @param left - Left index
 * @param right - Right index
 */
function binarySearch(arr, searchElement, left, right) {

  let mid = Math.floor((left + (right + 1)) / 2); // using floor as we may get floating numbers

  if (left <= right) { // If it is not the last element, process further, else return -1
    if (arr[mid] === searchElement) { // element found at mid
      return mid; // no need to process further
    } else if (searchElement < arr[mid]) { // element might be in first half
      right = mid - 1; // right is mid - 1 because we know that mid is not correct element
    } else { // element might be in second half
      left = mid + 1; // left is mid + 1 because we know that mid is not correct element
    }
    return this.binarySearch(arr, searchElement, left, right); // recursive
  }

  return -1; // element not found
}


// Invoking
console.log(binarySearch([1,2,3,4,5], 2, 0, 4));

Non-Recursive way

/**
 * Binary Search - Without using recursive
 * @param arr - Input Array
 * @param searchElement - Element to search
 */
function binarySearch(arr, searchElement) {

  let left = 0,
    right = arr.length - 1;

  while (left <= right) { // Process until it is last element

    let mid = Math.floor((left + (right + 1)) / 2); // using floor as we may get floating numbers

    if (arr[mid] === searchElement) { // element found at mid
      return mid; // no need to process further
    }
    if (searchElement < arr[mid]) { // element might be in first half
      right = mid - 1; // right is mid - 1 because we know that mid is not correct element
    } else { // element might be in second half
      left = mid + 1; // left is mid + 1 because we know that mid is not correct element
    }
  }

  return -1; // element not found
}

// Invoking
console.log(binarySearch([1, 2, 3, 4, 5], 2));

Upvotes: 2

Ctpelnar1988
Ctpelnar1988

Reputation: 1255

A recursive binary-search function that will return the index of the element being searched for:

function binarySearch(arr, target, idx=0){
  let full_len = arr.length;
  if(full_len === 0){
    return null;
  }
  let mid = Math.floor(full_len / 2);
  if(arr[mid] === target){
    return `INDEX of ${target} is: ${idx+mid}`;
  }else if(target > arr[mid]){
    let right = arr.slice(mid + 1, full_len);
    idx += (full_len - right.length);
    return binarySearch(right, target, idx);
  }else if(target < arr[mid]){
    let left = arr.slice(0, mid);
    return binarySearch(left, target, idx);
  }
}

//Testing:

var arr = [1, 27, 34, 42, 58, 69, 71, 85, 96, 151];
console.log(binarySearch(arr, 1)); //=> 0
console.log(binarySearch(arr, 27)); //=> 1
console.log(binarySearch(arr, 34)); //=> 2
console.log(binarySearch(arr, 42)); //=> 3
console.log(binarySearch(arr, 58)); //=> 4
console.log(binarySearch(arr, 69)); //=> 5
console.log(binarySearch(arr, 71)); //=> 6
console.log(binarySearch(arr, 85)); //=> 7
console.log(binarySearch(arr, 96)); //=> 8
console.log(binarySearch(arr, 151)); //=> 9
arr = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];
console.log(binarySearch(arr, 10)); //=> 0
console.log(binarySearch(arr, 20)); //=> 1
console.log(binarySearch(arr, 30)); //=> 2
console.log(binarySearch(arr, 40)); //=> 3
console.log(binarySearch(arr, 50)); //=> 4
console.log(binarySearch(arr, 60)); //=> 5
console.log(binarySearch(arr, 70)); //=> 6
console.log(binarySearch(arr, 80)); //=> 7
console.log(binarySearch(arr, 90)); //=> 8
console.log(binarySearch(arr, 100)); //=> 9

var bigArr = [];
for(var i = 1; i <= 1000000; i++){
  bigArr.push(i);
}
console.log(binarySearch(bigArr, 5342)) //=> 5341
console.log(binarySearch(bigArr, 254369)) //=> 254368
console.log(binarySearch(bigArr, 2000000)) //=> null
console.log(binarySearch(bigArr, -1)) //=> null

Upvotes: 1

georg
georg

Reputation: 214949

A variation of this problem is finding an element closest to the search X if there's no exact match.

To do that, we adapt @Alexander Ryzhov's answer so that it always returns the "insertion point" = index of the smallest of those elements that are greater than or equal to X.

Once we get the result index I, we check the elements at I (which might be X or greater than X) and I-1 (which is smaller) and choose the closest among the two. Don't forget to handle edge cases!

function binarySearch(a, compare) {
    let le = 0,
        ri = a.length - 1;

    while (le <= ri) {
        let mid = (le + ri) >> 1,
            cmp = compare(a[mid]);

        if (cmp > 0) {
            le = mid + 1;
        } else if (cmp < 0) {
            ri = mid - 1;
        } else {
            return mid;
        }
    }

    return le;
}


function binaryClosest(a, compare) {
    let i = binarySearch(a, compare);

    if (i === 0)
        return a[0];

    if (i === a.length)
        return a[i - 1];

    let d1 = -compare(a[i]),
        d2 = compare(a[i - 1]);

    return d1 < d2 ? a[i] : a[i - 1];
}


//

input = [-3, -2, -1, 0, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3]
findX = x => binaryClosest(input, item => x - item)

test = (exp, arg) => {
    let x = findX(arg)
    console.log(exp === x ? 'ok' : 'FAIL', arg, exp, x)
};

test(-3, -99)
test(+3, +99)

test(0, +0.3)
test(0, 0)
test(0, -0.3)

test(-1, -1.3)
test(+1, +1.3)

test(2, 2.2)
test(2, 2.3)
test(2, 2.5)
test(3, 2.6)

Upvotes: 2

Nikolay Makhonin
Nikolay Makhonin

Reputation: 1347

Full featured binarySearch:

  • Negative value is indicate the insertion point
  • Allow to search first and last index
  • start index, exclusive end index
  • Custom compare function

(this code and unit test here)

function defaultCompare(o1, o2) {
    if (o1 < o2) {
        return -1;
    }
    if (o1 > o2) {
        return 1;
    }
    return 0;
}

/**
 * @param array sorted array with compare func
 * @param item search item
 * @param start (optional) start index
 * @param end (optional) exclusive end index
 * @param compare (optional) custom compare func
 * @param bound (optional) (-1) first index; (1) last index; (0) doesn't matter
 */
function binarySearch(array, item, start, end, compare, bound) {
    if (!compare) {
        compare = defaultCompare;
    }
    let from = start == null ? 0 : start;
    let to = (end == null ? array.length : end) - 1;
    let found = -1;
    while (from <= to) {
        const middle = (from + to) >>> 1;
        const compareResult = compare(array[middle], item);
        if (compareResult < 0) {
            from = middle + 1;
        }
        else if (compareResult > 0) {
            to = middle - 1;
        }
        else if (!bound) {
            return middle;
        }
        else if (bound < 0) {
            // First occurrence:
            found = middle;
            to = middle - 1;
        }
        else {
            // Last occurrence:
            found = middle;
            from = middle + 1;
        }
    }
    return found >= 0 ? found : -from - 1;
}

Upvotes: -1

Rakesh Chaudhari
Rakesh Chaudhari

Reputation: 3502

I think below option is simple to implement binary search in JS.

arr = [1,2,3,4,5];
searchTerm=2;
function binarySearchInJS(start,end)
{
    isFound=false;
    if(end > start)
    {
        //console.log(start+"\t"+end)
        mid =  (end+start)/2;

        mid = Math.floor(mid)

        if(searchTerm==arr[mid])
        {                   
              isFound = true;             
        }
        else
        {   

            if(searchTerm < arr[mid])
            {               
                binarySearchInJS(start,mid);
            }
            if(searchTerm > arr[mid])
            {           
                binarySearchInJS(mid+1,end);
            }
        }
    }

    if(isFound)
    {
        return "Success";   
    }
    else{
            return "Not Found"; 
    }       
}

Upvotes: -1

joki
joki

Reputation: 6879

There are many workable solutions to this question, but all of them return early once they have found a match. While this might have a small positive effect on performance, this is negligible due to the logarithmic nature of binary search and can actually hurt performance if the comparison function is expensive to compute.

What is more, it prevents a very useful application of the binary search algorithm: finding a range of matching elements, also known as finding the lower or upper bound.

The following implementation returns an index 0 ≤ i ≤ array.length such that the given predicate is false for array[i - 1] and true for array[i]. If the predicate is false everywhere, array.length is returned.

/**
 * Return 0 <= i <= array.length such that !pred(array[i - 1]) && pred(array[i]).
 */
function binarySearch(array, pred) {
    let lo = -1, hi = array.length;
    while (1 + lo < hi) {
        const mi = lo + ((hi - lo) >> 1);
        if (pred(array[mi])) {
            hi = mi;
        } else {
            lo = mi;
        }
    }
    return hi;
}

Assume for the sake of argument that pred(array[-1]) === false and pred(array[array.length]) === true (although of course the predicate is never evaluated at those points). The loop maintains the invariant !pred(array[lo]) && pred(array[hi]). The algorithm terminates when 1 + lo === hi which implies !pred(array[hi - 1]) && pred(array[hi]), the desired postcondition.

If an array is sort()ed with respect to a comparison function compare, the function returns the smallest insert position of an item when invoked as

binarySearch(array, j => 0 <= compare(item, j));

An insert position is an index at which an item would be found if it existed in the array.

It is easy to implement lower and upper bound for an array in natural ordering as follows.

/**
 * Return i such that array[i - 1] < item <= array[i].
 */
function lowerBound(array, item) {
    return binarySearch(array, j => item <= j);
}

/**
 * Return i such that array[i - 1] <= item < array[i].
 */
function upperBound(array, item) {
    return binarySearch(array, j => item < j);
}

Of course, this is most useful when the array can contain several elements that compare identically, for example where elements contain additional data that is not part of the sort criteria.

Upvotes: 39

Shimon Doodkin
Shimon Doodkin

Reputation: 4569

to use it, just copy paste it as-is, to use local variables for speed. and modify the searched value like if you search in sub objects or arrays:

if (array[mid][0] < value[0]) low = mid + 1;
if (array[mid].val < value.val) low = mid + 1;

for faster results use arrays or arrays of arrays or parallel arrays, copy searched arrays to local variables. nonlocal variables or each time you do obj.something it slows down.

this is the fastest version is like this: 

let array=[3,4,5,6]
let value=5; //searched value
let mid, low = 0,high = array.length;
while (low < high) {
    mid = low + high >>> 1; // fast divide by 2 and round down
    if (array[mid] < value) low = mid + 1;
    else high = mid;
}
//if (array[mid] != value) mid=-1;// this might not be required if you look for place to insert new value
mid;// contains the found value position or if not found one before where it would be if it was found

binary search works like this:

|           .           |     // find middle
//option 1:
|           .     v     |     // if value on right, middle is top
            |     .     |     // so then it is like this
//option 2:                    
|     v     .           |     // if value on left, middle is bottom
|     .     |                 // so then it is like this
//more loops of option 2 until not found
|  .  |                       // next time it will be like this
|. |                          // next time it will be like this
.                             // next time it will be like this

this implementation goes to the bottom if not found. it could be found or not found always. it returns the index below or equals to the searched value. so you need to check if it equals. to validate if the value exists or it is just one result below. if you are looking for a place to insert inn order just put at that place, no need to check if equals

Upvotes: -1

ikrabbe
ikrabbe

Reputation: 1929

I want to add my searchArray binary search function, together with tool utility functions insertSortedArray and removeSortedArray to the list of answers, as I think it's clean, it is of global usage and I think it is quite speed optimal.

Upvotes: -2

sg28
sg28

Reputation: 1387

Let's assume the array is sorted (either write ur own sorted algorithm or just use inbuilt methods)

function bSearch(array,item){
  var start = 0,
  end = item.length - 1;
  var middle = Math.floor((end+start)/2);
  while(array[middle] !== item && start < end){
    if(item < array[middle]){
      end = middle-1;
     }
    else if(item > array[middle]){
      start = middle+1;
     }
     middle = Math.floor((end+start)/2);

  } 
  if(array[item]!== middle){
     console.log('notFoundMate);
     return -1;
  }
  else {
     console.log('FoundMate);
     return middle;
  }
}

Upvotes: -1

Ashvin777
Ashvin777

Reputation: 1482

function binarySearch(arr, num, l, r){
	if( arr instanceof Array ){
  	
    l = isNaN(l) ? 0 : l;
    r = isNaN(r) ? arr.length - 1: r;
    let mid = l + 1 + Math.round((r - l)/2 - 1);    
    console.log(l, r, mid, arr[mid]);
    
    if( num == arr[mid] ){ 
    	console.log("found"); 
      return mid; 
    }
    
    if( typeof arr[mid] == "undefined" || l == r ){
    	console.log("not found"); return -1;
    }
    
    if( num < arr[mid] ){  
    	console.log("take left"); 
      return binarySearch(arr, num, l, r - mid);
    }
    
    console.log("take right");
    return binarySearch(arr, num, mid, r);
    
  }
}

console.log( binarySearch([0, 0, 1 ,1, 2, 3, 5, 6, 11], 2) );

Upvotes: -1

Ashutosh Jha
Ashutosh Jha

Reputation: 16337

Here is the binary search function , you can check 

   function bsearch (Arr,value){
        var low  = 0 , high = Arr.length -1 ,mid ;      
        while (low <= high){
            mid = Math.floor((low+high)/2);     
            if(Arr[mid]==value) return mid ; 
            else if (Arr[mid]<value) low = mid+1;
            else high = mid-1;          
        }
        return -1 ;
    }

Upvotes: 12

trincot
trincot

Reputation: 350147

Here is an ES6 function in functional programming style, that uses a default compare function if none provided: if the value looked for is of the number type, numeric comparison will be assumed, otherwise string comparison.

function binarySearch(arr, val, compFunc = 
    (a, b) => typeof val == 'number' ? a-b : a.localeCompare(b), i=0, j=arr.length) {
  return i >= j ? i
    : ( mid =>
          ( cmp => 
              cmp < 0 ? binarySearch(arr, val, compFunc, i, mid) 
            : cmp > 0 ? binarySearch(arr, val, compFunc, mid+1, j) 
            : mid 
          ) (compFunc(val, arr[mid]))
      ) (i + j >> 1);
}

///////// Tests ///////////////////

function check(arr, val, compFunc) {
  var fmt = JSON.stringify;
  var result = binarySearch(arr, val); // default compFunc is assumed
  console.log(`binarySearch(${fmt(arr)}, ${fmt(val)}) == ${fmt(result)}`);
  if (result > arr.length || result < 0 || !arr.length && result 
    || result < arr.length && compFunc(val, arr[result]) > 0
    || result > 0 && compFunc(val, arr[result-1]) < 0) throw "Unexpected result!!!"
}

// Tests with numeric data:
for (var val = 0; val < 12; val++)      
  check([1, 2, 4, 6, 9, 9, 10], val, (a,b) => a-b);
// Test with empty array:
check([], 12, (a,b) => a-b);
// Test with string data:
check(['abc', 'deaf', 'def', 'g'], 'dead', (a, b) => a.localeCompare(b));

Upvotes: 0

Jeremy Noel
Jeremy Noel

Reputation: 7

Good afternoon, I understand this post started some time ago, however I thought I could possibly contribute to the discussion.

function binarySearch(array, target, max, min) {

    //Find the Midpoint between forced max and minimum domain of the array
    var mid = ((max - min) >> 1) + min;
    //alert("Midpoint Number" + mid);
    console.log(mid);
    console.log(array[mid], "target: " + target);

    if (array[mid] === target) {
        //Target Value found
        console.log('match', array[mid], target);
        //alert('match', array[mid], target);
        return mid;
    } 
    else if (mid === 0)
    {
        //All Value have been checked, and none are the target value, return sentinel value
        return -1;
    }
    else if (array[mid] > target)
    {
        //Value at Midpoint is greater than target Value, set new maximum to current midpoint
        max = mid;
        console.log('mid lower', array[mid], target);
        //alert('mid lower', array[mid], target);
        //Call binarySearch with new search domain
        return binarySearch(array, target, max, min);
    } 

    else if (array[mid] < target)
    {
        // Value at Midpoint is less than the target Value, set new minimum to current midpoint
        min = mid;
        console.log('mid higher', array[mid], target);
        //alert('mid higher', array[mid], target);

        //Call binarySearch with new search domain
        return binarySearch(array, target, max, min);
    }

I am sure there is room for refinement here, but this method prevents having to perform a deep copy of the array (which can be a costly action when working with a large data set) and at the same time, it does not modify the array in any way.

Hope that helps! Thanks, Jeremy

Upvotes: -1

Jannic Beck
Jannic Beck

Reputation: 2425

function binarySearch(a = [], x) {
    let length = a.length;
    if (length === 0) {
        return false;
    } else {
        let m = Math.floor(length/2);
        let y = a[m];
        if (x === y) {
            return true;
        } else if (x < y) {
            return binarySearch(a.slice(0, m), x);
        } else {
            return binarySearch(a.slice(m + 1), x);
        }
    }
}

Upvotes: -1

adkelley
adkelley

Reputation: 48

You should also check for the "value not found" edge case, and make it your first base condition, followed by a successful search. Consequently you do not need to check for array length > 1 when recursing through the array. Finally, since you don't return the array, why not use the Array.prototype.slice method?

var binarySearch = function(arr, val) {
  var half = Math.floor(arr.length / 2);

  if (arr.length === 0) {
    return -1;
  }
  else if (arr[half] === val) {
    console.log("val: ", val, "arr[half]: ", arr[half]);
    return val;
  }
  else if (val > arr[half]) {
    console.log("val: ", val, "arr[half]: ", arr[half]);
    return binarySearch(arr.slice(half, arr.length), val);
  }
  else {
    console.log("val: ", val, "arr[half]: ", arr[half]);
    return binarySearch(arr.slice(0, half), val);
  }
}


var arr = [1, 5, 20, 58, 76, 8, 19, 41].sort(function(a, b) { return a - b });

console.log("Sorted array: " + arr);
console.log(binarySearch(arr, 76));
console.log(binarySearch(arr, 19));
console.log(binarySearch(arr, 0));

Upvotes: -1

Zack
Zack

Reputation: 1703

Assuming a sorted array, here's a recursive binary search:

function binSearch(needle, arr) {
  length = arr.length;
  while(length > 1) {
    midpoint = Math.floor(length/2);
    return (needle > arr[midpoint-1]) ? 
           binSearch(needle, arr.splice(midpoint, length)) :    
           binSearch(needle, arr.splice(0, midpoint));
  }
  return needle === arr[0] ? arr[0] : -1;
}

Upvotes: -1

fstasi
fstasi

Reputation: 77

This is my solution!

// perform a binarysearch to find the position in the array
function binarySearch(searchElement, searchArray) {
    'use strict';

    var stop = searchArray.length;
    var last, p = 0,
        delta = 0;

    do {
        last = p;

        if (searchArray[p] > searchElement) {
            stop = p + 1;
            p -= delta;
        } else if (searchArray[p] === searchElement) {
            // FOUND A MATCH!
            return p;
        }

        delta = Math.floor((stop - p) / 2);
        p += delta; //if delta = 0, p is not modified and loop exits

    }while (last !== p);

    return -1; //nothing found

};

Upvotes: 1

Eliran Malka
Eliran Malka

Reputation: 16263

You're not explicitly returning the recursive inner calls (i.e. return binarySearch()), so the call stack unfolds with no return value. Update your code like so:

// ...
if (arr[mid] === i) {
    console.log('match', arr[mid], i);
    return arr[mid];
} else if (arr[mid] < i && arr.length > 1) {
    console.log('mid lower', arr[mid], i);
    return binarySearch(arr.splice(mid, Number.MAX_VALUE), i);
} else if (arr[mid] > i && arr.length > 1) {
    console.log('mid higher', arr[mid], i);
    return binarySearch(arr.splice(0, mid), i);
} else {
// ...

See a working fiddle

Upvotes: 27

Related Questions