Drill 26: Improve it — Binary search

function binarySearch(sorted, target) {
  let low = 0
  let high = sorted.length - 1

  while (low <= high) {
    const mid = Math.floor((low + high) / 2)
    if (sorted[mid] === target) return mid
    if (sorted[mid] < target) low = mid + 1
    else high = mid - 1
  }
  return -1
}

function lowerBound(sorted, target) {
  let low = 0
  let high = sorted.length
  while (low < high) {
    const mid = Math.floor((low + high) / 2)
    if (sorted[mid] < target) low = mid + 1
    else high = mid
  }
  return low
}

console.log(binarySearch([1, 3, 5, 7, 9], 7))
console.log(lowerBound([1, 3, 3, 3, 5], 3))