quicksort, mergesort, heapsort, binary search, depth-first, and breadth-first search

binary-search.js

function binarySearch(target, sortedArray, start = -1, end = -1) {
  if (start < 0) {
    start = 0;
  }
  if (end < 0) {
    end = sortedArray.length;
  }
  let halfDist = sortedArray.length;
  let centerIndex = 0;
  let center = 0;

  while (halfDist > 1) {
    halfDist = Math.round((end - start) / 2);
    centerIndex = start + halfDist;
    center = sortedArray[centerIndex];

    if (target === center) {
      return centerIndex;
    }
    if (target < center) {
      end = start + halfDist;
    }
    if (target > center) {
      start = start + halfDist;
    }
  }

  return -1;
}

// TEST:
function test() {
  const testArray = (len) => {
    return new Array(len).fill(1).map((_, i) => i);
  };

  console.assert(binarySearch(10, testArray(100)) == 10, 'Should be index 10');
  console.assert(binarySearch(999, testArray(100)) == -1, 'Should be index -1');
  console.assert(
    binarySearch(10, testArray(10000000)) === 10,
    'Should be index 10'
  );
  console.assert(
    binarySearch(999998, testArray(10000000)) === 999998,
    'Should be index 999998'
  );
}

test();

breadth-first-search.js

// TODO

depth-first-search.js

// TODO

heaps.js

class MinHeap {
  constructor() {
    this.heap = [null];
  }

  getMin() {
    return this.heap[1];
  }

  insert(node) {
    this.heap.push(node);

    if (this.heap.length > 1) {
      let current = this.heap.length - 1;
      while (
        current > 1 &&
        this.heap[Math.floor(current / 2)] > this.heap[current]
      ) {
        this.swap(this.heap, current, Math.floor(current / 2));
        current = Math.floor(current / 2);
      }
    }
  }

  swap(arr, iA, iB) {
    [arr[iB], arr[iA]] = [arr[iA], arr[iB]];
    return arr;
  }
}

class MaxHeap {
  constructor() {
    this.heap = [null];
  }

  getMax() {
    return this.heap[1];
  }

  insert(node) {
    this.heap.push(node);

    if (this.heap.length > 1) {
      let current = this.heap.length - 1;
      while (
        current > 1 &&
        this.heap[Math.floor(current / 2)] > this.heap[current]
      ) {
        this.swap(this.heap, current, Math.floor(current / 2));
        current = Math.floor(current / 2);
      }
    }
  }

  swap(arr, iA, iB) {
    [arr[iB], arr[iA]] = [arr[iA], arr[iB]];
    return arr;
  }
}

function heapify(arr) {
  let heap = new Heap();

  arr.forEach((item) => {
    heap.insert(item);
  });

  return heap;
}

function test() {
  const scramble = (arr) => {
    arr.sort((a, b) => {
      return Math.random() * 2 - Math.random() * 2;
    });
    return arr;
  };

  const genArray = (len) => {
    return new Array(len).fill(1).map((_, i) => i);
  };

  const testArray = scramble(genArray(100));
  const myHeap = heapify([...testArray]);

  console.log(testArray, myHeap.getMin(), myHeap.getMax());
}

test();

/* 

Heap indexes

             1
         /        \
        2          3
       / \       /   \
      4   5     6     7
     /\   /\    /\    /\
    8  9 10 11 12 13 14 15
          



*/

heapsort.js

// TODO

mergesort.js

// TODO

quicksort.js

// TODO