JSFiddle - React, Tailwind, and code Playground

by Bartosz Zieliński

JavaScript

function find(array, point) {
    var idx = -1;
    
    var start = 0;
    var end = array.length-1;
    var mid = Math.floor(end/2);
    
    while (start <= end) {
			var p1 = array[mid][0];
      var p2 = array[mid][1];
      
      if (point < p1) {
      	end = mid - 1;
      } else if (point >= p1 && point < p2) {
	    	return {
        	idx: mid,
          outside: false
        }
      } else {
   	  	start = mid + 1;
      }
      mid = Math.floor((start + end) / 2);
    }
    
    if (start > array.length-1) {
    	return {
      	idx: array.length,
        outside: true
      }
    }
    
    return {
    	idx: Math.max(0,start-1),
      outside: true
    };
}

function find2(array, point) {
    var idx = -1;
    for (var i = 0; i < array.length; i++) {
        var p1 = array[i][0];
        var p2 = array[i][1];

        if (point < p1) {
            return {
                idx: Math.max(i-1,0),
                outside: true
            };
        } else if (point >= p1 && point < p2) {
            return {
                idx: i,
                outside: false
            }
        }
    }

    return {
        idx: array.length,
        outside: true
    }
}

console.log("Performance in small array");
var a = [[1,3], [3,5], [7,9],[12,20],[21,22],[22,23],[24,25],[30,40]];
var max=45;
// conformance tests
for (var i = 0; i < max; i++) {
	var r1 = find(a, i);
	var r2 = find2(a, i);
  if (r1.idx !== r2.idx) {
     throw new Error("Wrong idx ", i);
  }
  if (r1.outside !== r2.outside) {
  	 throw new Error("Wrong outsideness ", i);
  }
}

var reps = 1000000;
// performance in short array
var now = Date.now();
for (var j = 0; j < reps; j++ ) {
for (var i = 0; i < max; i++) {
	find(a, i);
}
}
console.log("p1: " + (Date.now()-now));

now = Date.now();
for (var j = 0; j < reps; j++ ) {
for (var i = 0; i < max; i++) {
	find2(a, i);
}
}
console.log("p2: " + (Date.now()-now));

console.log("Performance in medium array");
var b =...