binary_search ipv4

(async function ipv4Benchmark() {
  function ipToInt(ip) {
    return ip.split('.').reduce((acc, octet) => (acc << 8) + parseInt(octet, 10), 0) >>> 0;
  }

  function intToIp(int) {
    return [24, 16, 8, 0].map(shift => (int >>> shift) & 255).join('.');
  }

  function generateRandomIP() {
    return Array(4).fill(0).map(() => Math.floor(Math.random() * 256)).join('.');
  }

  function binarySearch(arr, val) {
    let low = 0, high = arr.length - 1;
    while (low <= high) {
      const mid = (low + high) >>> 1;
      const midVal = arr[mid];
      if (midVal === val) return true;
      else if (midVal < val) low = mid + 1;
      else high = mid - 1;
    }
    return false;
  }

  const log = console.log;
  const ipCount = 5_000_000;
  const checkCount = 1_000_000;

  log("Generating ip list");
  const startGen = performance.now();

  const ipSet = new Set();
  while (ipSet.size < ipCount) {
    ipSet.add(ipToInt(generateRandomIP()));
    if (ipSet.size % 100_000 === 0) log(`...${ipSet.size} done`);
  }

  const ipArray = new Uint32Array([...ipSet].sort((a, b) => a - b));
  const genTime = (performance.now() - startGen).toFixed(1);
  log(`Generated sorted IPs in ${genTime} ms`);

  log("Generating test IPs (50% hits, 50% likely misses)...");
  const testIPs = [];
  for (let i = 0; i < checkCount / 2; i++) {
    testIPs.push(ipArray[Math.floor(Math.random() * ipArray.length)]);
  }
  for (let i = 0; i < checkCount / 2; i++) {
    testIPs.push(ipToInt(generateRandomIP()));
  }
  testIPs.sort(() => Math.random() - 0.5);

  log("Starting binary searches...");
  await new Promise(r => setTimeout(r, 100)); // allow rendering if needed

  const startSearch = performance.now();
  let found = 0;
  for (let ip of testIPs) {
    if (binarySearch(ipArray, ip)) found++;
  }
  const searchTime = (performance.now() - startSearch).toFixed(1);

  log(`Search complete in ${searchTime} ms`);
  log(`Found: ${found} / ${checkCount}`);
})();