binary-search.js

/**
 * As part of a technical screening interview I was requested to create a function
 * able to perform a binary search.
 *
 * @param {Number[]} arr - A sorted array
 * @param {Number} k - Number to find
 * @return {Number} index position where k was found in the array
 *
 * @see: https://en.wikipedia.org/wiki/Binary_search_algorithm
 */

function binarySearch (arr, k) {
  if (arr.length === 1) {
    return 0
  }

  const middle = Math.floor(arr.length / 2)

  const sideA = arr.slice(0, middle)
  const sideB = arr.slice(middle)

  const isSideAValid = sideA.slice(-1)[0] >= k
  const offset = isSideAValid ? 0 : middle

  return binarySearch(isSideAValid ? sideA : sideB, k) + offset
}

const arr = [1, 4, 7, 9, 10, 13, 18, 21, 24]

// test
arr.forEach((n, i) => {
  console.log(n, binarySearch(arr, n) === i ? '' : 'NOT', `found as expected in position ${ i }`)
})

// 1  found as expected in position 0
// 4  found as expected in position 1
// 7  found as expected in position 2
// 9  found as expected in position 3
// 10  found as expected in position 4
// 13  found as expected in position 5
// 18  found as expected in position 6
// 21  found as expected in position 7
// 24  found as expected in position 8