Binary Search

// Template 1: exact match on a sorted array.
// Invariant: if target is anywhere in nums, it is inside nums[lo..hi] (both ends included).
export function binarySearch(nums, target) {
  let lo = 0;
  let hi = nums.length - 1;
  while (lo <= hi) {                       // the range is not empty
    const mid = Math.floor((lo + hi) / 2); // rounds down; exact for any index in JS
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) lo = mid + 1;  // mid and everything left of it are too small
    else hi = mid - 1;                     // mid and everything right of it are too big
  }
  return -1;                               // empty range: target is not in nums
}

// Template 2: first true. ok(i) must be false for a prefix of [lo, hi) and true for the rest.
// Returns the first i with ok(i), or hi if there is none. Invariant: the answer is always in [lo, hi].
export function firstTrue(lo, hi, ok) {
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2); // lo <= mid < hi, so both updates shrink the range
    if (ok(mid)) hi = mid;                 // mid might be the first true: keep it
    else lo = mid + 1;                     // mid is false, and so is everything before it
  }
  return lo;                               // lo === hi
}

// First index with nums[i] >= target, or nums.length: the first copy of target, or where it would be inserted.
export function lowerBound(nums, target) {
  return firstTrue(0, nums.length, (i) => nums[i] >= target);
}

// First index with nums[i] > target: one past the last copy of target.
export function upperBound(nums, target) {
  return firstTrue(0, nums.length, (i) => nums[i] > target);
}

// How many values lie in [low, high]? Two bounds, O(log n), no scanning.
export function countInRange(nums, low, high) {
  return Math.max(0, upperBound(nums, high) - lowerBound(nums, low));
}

// Template 3: a sorted array of distinct values, rotated. Returns the index of the minimum (where the rotation starts).
// Compare with nums[hi]: if nums[mid] > nums[hi], the drop, and so the minimum, is to the right of mid.
export function findMinIndex(nums) {
  let lo = 0;
  let hi = nums.length - 1;
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (nums[mid] > nums[hi]) lo = mid + 1; // mid is in the upper run: the minimum comes after it
    else hi = mid;                          // mid is in the lower run: the minimum is mid or before it
  }
  return lo;
}

// Template 4: binary search on the answer. The answer is a number in [lo, hi], and "does x work?"
// flips from false to true exactly once as x grows. Here: the smallest ship capacity that delivers
// every package, in order, within `days` days.
export function shipWithinDays(weights, days) {
  const daysNeeded = (cap) => {
    let used = 1;
    let load = 0;
    for (const w of weights) {
      if (load + w > cap) {   // this package doesn't fit today: start a new day
        used++;
        load = 0;
      }
      load += w;
    }
    return used;
  };
  let lo = Math.max(...weights);                // anything smaller can't carry the heaviest package
  let hi = weights.reduce((a, b) => a + b, 0);  // everything in one day always works
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (daysNeeded(mid) <= days) hi = mid;      // works: the answer is mid or smaller
    else lo = mid + 1;                          // too small: the answer is bigger
  }
  return lo;
}

// "Maximize the minimum": the largest gap such that k items (2 <= k <= positions.length) can sit at
// distinct positions with every two of them at least `gap` apart. Here "works" goes true...true, false...false,
// so search for the first gap that fails and step back by one.
export function maxMinDistance(positions, k) {
  const sorted = [...positions].sort((a, b) => a - b);
  const canPlace = (gap) => {
    let placed = 1;
    let last = sorted[0];
    for (const p of sorted) {
      if (p - last >= gap) {  // greedy: take the earliest position that is far enough
        placed++;
        last = p;
      }
    }
    return placed >= k;
  };
  let lo = 1;                                   // a gap of 1 always works
  let hi = sorted.at(-1) - sorted[0] + 1;       // wider than the whole span: always fails
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (!canPlace(mid)) hi = mid;               // first failing gap is mid or smaller
    else lo = mid + 1;
  }
  return lo - 1;                                // the last gap that works
}