JSFiddle - React, Tailwind, and code Playground

"Half Life" Array Search - Find an item in a sorted array that contains thousands of items by repeatedly eliminating half of the items.

by skibulk

JavaScript

console.clear();

/*
Index 20
-----
regularSearch - 1x
halfLifeSearch - 0.4x

Index 200
-----
regularSearch - 1x
halfLifeSearch - 1x

Index 2,000
-----
regularSearch - 1x
halfLifeSearch - 7x

Index 20,000
-----
regularSearch - 1x
halfLifeSearch - 75x
*/

var target = 10000000;

var options = [[0]];
var last = 0;
var size = 1000 * 1000; // 1 Million

for(var i = 0; i < size; i++){
	last += Math.round(Math.random()*100);
	options.push([last]);
}

console.log("Data Loaded", options);

function regularSearch(target, options){
	for(var i = 0; i < options.length; i++){
  	if(options[i][0] > target){
    	return [i-1, options[i-1]];
    }
  }
}

function halfLifeSearch(target, options)
{
	// if(options && options.length && options[0] && Number.isInteger(options[0][0]) && target >= options[0][0])
  return halfLoop(0, options.length);

  function halfLoop(min, max){
    
    if(min < max)
    {
      var half = min+Math.floor((max-min)/2);
  		// console.log("loop", min, max, half, options[half][0]);

      if(target < options[half][0])
      {
        return halfLoop(min, half-1);
      }
      else if(target > options[half][0])
      {
        return halfLoop(half+1, max);
      }
      else
      {
				// console.log("loop mid", options[half], options[half+1]);
	      return [half, options[half]];
      }
    }

    // min == max
    if(target < options[min][0])
    {
			// console.log("loop low", options[min-1], options[min]);
      return [min-1, options[min-1]];
    }
    else
    {
			// console.log("loop high", options[min], options[min+1]);
      return [min, options[min]];
    }
  }
}

// BENCHMARK -----------

function benchmark(func){
	var iterations = 0;
	var now;
  var startTime = Date.now();
  var stopTime = Date.now() + 1000;
  do {
  	func();
    iterations++
    now = Date.now();
  } while (now < stopTime)
  
  iterations = Math.round(iterations * (stopTime / now));
  if(!benchmark.baseline) benchmark.baseline = iterations;
  var result =...