binary search vs loop (v16)

Revision 16 of this benchmark created on

Description

Looks at the performance difference between brute force searching and binary search.

Preparation HTML

<script>
  var arr = new Array();
  for (var i = 0; i < 2000; ++i) {
   arr[i] = i;
  }
</script>

Test runner

Ready to run.

Testing in
TestOps/sec
binarySearchFast
var search= Math.floor(Math.random() * arr.length);
var searchArr = arr;

      
      var size = searchArr .length,
          high = size -1,
          low = 0;
      
      while (high > low) {
        
        if (searchArr[low] === search) return low;
        else if (searchArr[high] === search) return high;
    
        target = (((search - searchArr[low]) / (searchArr[high] - searchArr[low])) * (high - low)) >>> 0;
    
        if (searchArr[target] === search) return target;
        else if (search > searchArr[target]) low = target + 1, high--;
        else high = target - 1, low++;
      }
      return -1;


  return null;
ready
binary math.floor
var find = Math.floor(Math.random() * arr.length);
var searchArr = arr;
  var low = 0, high = searchArr.length - 1, i, comparison;
  while (low <= high) {
    i = Math.floor((low + high) / 2);
    if (searchArr [i] < find) { low = i + 1; continue; };
    if (searchArr [i] > find) { high = i - 1; continue; };


    return i;
  }

  return null;
ready
binary bitshift
var find = Math.floor(Math.random() * arr.length);
var searchArr = arr;
  var low = 0, high = searchArr.length - 1, i, comparison;
  while (low <= high) {
    i = (low + high) >> 1;
    if (searchArr [i] < find) { low = i + 1; continue; };
    if (searchArr [i] > find) { high = i - 1; continue; };


    return i;
  }

  return null;
ready

Revisions

You can edit these tests or add more tests to this page by appending /edit to the URL.