BINARY_SEARCH

// BINARY_SEARCH.js — O(log n) time complexity
// Precondition: arr must be sorted in ascending order.
function binarySearch(arr, target) {
  let lo = 0;
  let hi = arr.length - 1;

  while (lo <= hi) {
    // Midpoint, written to avoid overflow on huge arrays
    const mid = lo + Math.floor((hi - lo) / 2);

    if (arr[mid] === target) {
      return mid; // Found — DECODED
    } else if (arr[mid] < target) {
      lo = mid + 1; // Target must be in the right half
    } else {
      hi = mid - 1; // Target must be in the left half
    }
  }

  return -1; // Not present
}