Binary Search Tree Start

bst.js

// `data` array contains 10 million random values
// and we want to a) determine whether or not a value is in the array, 
// and b) determine the value before and after

// tell us how long a function takes to run
function profile(name, fn) {
  console.log(`profiling ${name}`);
  let start = new Date();
  let out = fn();
  out && console.log(out);
  console.log(`${name} finished in ${new Date() - start}ms.`);
}

// run a function over and over again and calculate average run time
function benchmark(name, fn) {
  console.log(`profiling ${name}`);
  let result = fn();
  let start = new Date();
  for(var i = 0; i < 1000; i++) {
    fn();
  }
  result && console.log(result);
  const ms = (new Date() - start) / 1000;
  console.log(`${name} averaged ${ms}ms.`);
}

let data = [];
let count = 10 * 1000 * 1000; // number of data points we want to populate

profile('generate data', function() {
  for(let i = 0; i < count; i++) {
    data.push(Math.random());
  }
});

// arbitrary value we want to know is in the list
const testValue = 0.33;
// arbitrary random place to put it
const initialPosition = Math.floor(Math.random() * count);
data[initialPosition] = testValue;

benchmark('indexOf find', function() {
  return data.indexOf(testValue);
});

benchmark('random indexOf find', function() {
  const randValue = data[Math.floor(Math.random() * count) - 1];
  return data.indexOf(randValue);
});