Use binary search to find the index where the given element needs to be inserted into the given sorted array

lookupInsertionIndex.js

// use binary search to return index where given element needs to be inserted in the input array (must be sorted)
function binarySearchForInsertionIndex(arr, el, index = 0) {
  const mid = ~~(arr.length / 2)

  if (!arr.length || arr[mid] === el) return index

  if (el < arr[mid]) return binarySearchForInsertionIndex(arr.slice(0, mid), el, mid + index - 1)
  if (el > arr[mid]) return binarySearchForInsertionIndex(arr.slice(mid + 1), el, mid + index + 1)
}

// e.g., for arr = [1,2,3,5,6] and el = 4, this will return 3 which is the index you can insert 4 at in [1,2,3,5,6]
// so you can do something like the following: arr.splice(binarySearchForInsertionIndex(arr, 4), 0, 4)