Binary search with comparator

binary-search.js

// The default comparator is for any values that can be
// compared with '==', '<', '<=', '>', '>='.
function defaultComparator(candidate, target) {
  if (target < candidate) {
    return -1
  } else if (target > candidate) {
    return 1
  } else {
    return 0
  }
}

// Performs a search in O(log(n)) time.
function binarySearch(sortedList, target, low, high, comparator) {
  if (high < low) {
    return null
  }

  const mid = Math.floor(low + ((high - low) / 2))
  const result = comparator(sortedList[mid], target)

  if (result === 0) {
    return sortedList[mid]
  } else if (result < 0) {
    return binarySearch(sortedList, target, low, mid-1, comparator)
  } else {
    return binarySearch(sortedList, target, mid+1, high, comparator)
  }
}

const search = {
  binary(sortedList, target, comparator=defaultComparator) {
    return binarySearch(sortedList, target, 0, sortedList.length-1, comparator)
  }
}

function example() {
  const list = [0, 1, 2, 3, 4, 5, 6, 7]
    .map((item, index) => ({value: index}))
    .sort((a, b) => a.value - b.value)
  const searchFor = 5

  const found = search.binary(list, searchFor, (candidate, target) => {
    if (target < candidate.value) {
      return -1
    } else if (target > candidate.value) {
      return 1
    } else {
      return 0
    }
  })

  console.log('found', found)
}

module.exports = {
  search: search,
  example: example
}