// ─────────────────────────────────────────────────────────────────────────────
// BINARY SEARCH
// ─────────────────────────────────────────────────────────────────────────────
// WHAT   : halve a MONOTONIC search space each step.
// TELL   : "sorted", "O(log n)", "rotated sorted", "peak", "first/last occurrence",
//          "minimum X such that condition holds", "min capacity / max speed / split into k".
// SAY    : lower bound (first >= target), upper bound (first > target), invariant,
//          predicate / feasibility function, "binary search on the answer", monotone predicate.
// BIG-O  : O(log n) time, O(1) space; on-the-answer = O(n log(range)).
// ─────────────────────────────────────────────────────────────────────────────
'use strict';
const assert = require('node:assert/strict');

// ── TEMPLATE A: exact match (closed interval, lo <= hi)
//   lo = 0, hi = n-1
//   while lo <= hi:
//     mid = lo + ((hi - lo) >> 1)        // avoids overflow; >> 1 is integer halving
//     if a[mid] === target: return mid
//     if a[mid] < target: lo = mid + 1 else hi = mid - 1
//   return -1
//
// ── TEMPLATE B: first index where predicate(i) is true (half-open [lo, hi), lo < hi)
//   lo = 0, hi = n                      // hi = n means "none"
//   while lo < hi:
//     mid = lo + ((hi - lo) >> 1)
//     if pred(mid): hi = mid             // mid could be the answer; keep it
//     else: lo = mid + 1
//   return lo
//   -> lower bound = pred(i): a[i] >= t ; upper bound = pred(i): a[i] > t

// ── 1. Classic binary search  —  template A  —  O(log n) / O(1)
function binarySearch(a, target) {
  let lo = 0, hi = a.length - 1;
  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (a[mid] === target) return mid;
    if (a[mid] < target) lo = mid + 1; else hi = mid - 1;
  }
  return -1;
}
assert.equal(binarySearch([-1, 0, 3, 5, 9, 12], 9), 4);
assert.equal(binarySearch([-1, 0, 3, 5, 9, 12], 2), -1);
assert.equal(binarySearch([], 1), -1);

// ── 2. Lower bound / upper bound  —  template B  —  O(log n) / O(1)
function lowerBound(a, t) { // first i with a[i] >= t
  let lo = 0, hi = a.length;
  while (lo < hi) { const m = lo + ((hi - lo) >> 1); if (a[m] >= t) hi = m; else lo = m + 1; }
  return lo;
}
function upperBound(a, t) { // first i with a[i] > t
  let lo = 0, hi = a.length;
  while (lo < hi) { const m = lo + ((hi - lo) >> 1); if (a[m] > t) hi = m; else lo = m + 1; }
  return lo;
}
assert.equal(lowerBound([1, 2, 2, 2, 5], 2), 1);
assert.equal(upperBound([1, 2, 2, 2, 5], 2), 4); // count of 2s = upper - lower = 3
assert.equal(lowerBound([1, 3], 4), 2); // not found -> n
assert.equal(lowerBound([], 1), 0);

// ── 3. Search insert position  —  = lower bound  —  O(log n)
const searchInsert = lowerBound;
assert.equal(searchInsert([1, 3, 5, 6], 5), 2);
assert.equal(searchInsert([1, 3, 5, 6], 2), 1);
assert.equal(searchInsert([1, 3, 5, 6], 7), 4);

// ── 4. First bad version  —  template B over versions 1..n with pred = isBad  —  O(log n)
function firstBadVersion(n, isBad) {
  let lo = 1, hi = n;
  while (lo < hi) { const m = lo + ((hi - lo) >> 1); if (isBad(m)) hi = m; else lo = m + 1; }
  return lo;
}
assert.equal(firstBadVersion(5, (v) => v >= 4), 4);
assert.equal(firstBadVersion(1, (v) => v >= 1), 1);
assert.equal(firstBadVersion(10, (v) => v >= 10), 10);

// ── 5. Search in rotated sorted array  —  one half is always sorted; check if target is inside it  —  O(log n)
function searchRotated(a, t) {
  let lo = 0, hi = a.length - 1;
  while (lo <= hi) {
    const m = lo + ((hi - lo) >> 1);
    if (a[m] === t) return m;
    if (a[lo] <= a[m]) { // left half sorted
      if (a[lo] <= t && t < a[m]) hi = m - 1; else lo = m + 1;
    } else { // right half sorted
      if (a[m] < t && t <= a[hi]) lo = m + 1; else hi = m - 1;
    }
  }
  return -1;
}
assert.equal(searchRotated([4, 5, 6, 7, 0, 1, 2], 0), 4);
assert.equal(searchRotated([4, 5, 6, 7, 0, 1, 2], 3), -1);
assert.equal(searchRotated([1], 1), 0);

// ── 6. Find minimum in rotated sorted array  —  compare mid to hi; min is in the unsorted half  —  O(log n)
function findMin(a) {
  let lo = 0, hi = a.length - 1;
  while (lo < hi) {
    const m = lo + ((hi - lo) >> 1);
    if (a[m] > a[hi]) lo = m + 1; else hi = m;
  }
  return a[lo];
}
assert.equal(findMin([3, 4, 5, 1, 2]), 1);
assert.equal(findMin([1, 2, 3]), 1); // not rotated
assert.equal(findMin([2, 1]), 1);

// ── 7. Peak element  —  climb toward the larger neighbor; a[m] < a[m+1] -> peak on the right  —  O(log n)
function findPeak(a) {
  let lo = 0, hi = a.length - 1;
  while (lo < hi) {
    const m = lo + ((hi - lo) >> 1);
    if (a[m] < a[m + 1]) lo = m + 1; else hi = m;
  }
  return lo;
}
assert.equal(findPeak([1, 2, 3, 1]), 2);
assert.ok([1, 5].includes(findPeak([1, 2, 1, 3, 5, 6, 4])));
assert.equal(findPeak([7]), 0);

// ── TEMPLATE C: binary search on the answer
//   lo = smallest possible answer, hi = largest possible answer
//   while lo < hi: mid = ...; if feasible(mid): hi = mid else lo = mid + 1   // minimize
//   feasible() is a MONOTONE predicate: if x works, every x' > x works (or vice-versa for maximize).

// ── 8. Koko eating bananas  —  min speed k such that hours(k) <= h  —  O(n log max)
function minEatingSpeed(piles, h) {
  const feasible = (k) => piles.reduce((t, p) => t + Math.ceil(p / k), 0) <= h; // predicate
  let lo = 1, hi = Math.max(...piles);
  while (lo < hi) { const m = lo + ((hi - lo) >> 1); if (feasible(m)) hi = m; else lo = m + 1; }
  return lo;
}
assert.equal(minEatingSpeed([3, 6, 7, 11], 8), 4);
assert.equal(minEatingSpeed([30, 11, 23, 4, 20], 5), 30);
assert.equal(minEatingSpeed([1], 1), 1);

// ── 9. Min capacity to ship within D days  —  lo = max(w), hi = sum(w); feasible = days needed <= D  —  O(n log sum)
function shipWithinDays(weights, D) {
  const feasible = (cap) => { // greedy count of days at this capacity
    let days = 1, load = 0;
    for (const w of weights) { if (load + w > cap) { days++; load = 0; } load += w; }
    return days <= D;
  };
  let lo = Math.max(...weights), hi = weights.reduce((a, b) => a + b, 0);
  while (lo < hi) { const m = lo + ((hi - lo) >> 1); if (feasible(m)) hi = m; else lo = m + 1; }
  return lo;
}
assert.equal(shipWithinDays([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5), 15);
assert.equal(shipWithinDays([3, 2, 2, 4, 1, 4], 3), 6);
assert.equal(shipWithinDays([5], 1), 5);

// ── 10. Split array largest sum (into k parts)  —  same shape as shipping; feasible = pieces needed <= k  —  O(n log sum)
function splitArray(nums, k) {
  const feasible = (cap) => {
    let parts = 1, sum = 0;
    for (const x of nums) { if (sum + x > cap) { parts++; sum = 0; } sum += x; }
    return parts <= k;
  };
  let lo = Math.max(...nums), hi = nums.reduce((a, b) => a + b, 0);
  while (lo < hi) { const m = lo + ((hi - lo) >> 1); if (feasible(m)) hi = m; else lo = m + 1; }
  return lo;
}
assert.equal(splitArray([7, 2, 5, 10, 8], 2), 18);
assert.equal(splitArray([1, 2, 3, 4, 5], 2), 9);
assert.equal(splitArray([1], 1), 1);

// ── 11. Search a 2D matrix (rows sorted, row[0] > prev row last)  —  treat as flat array; r = i / cols, c = i % cols  —  O(log(mn))
function searchMatrix(mat, t) {
  if (mat.length === 0) return false;
  const rows = mat.length, cols = mat[0].length;
  let lo = 0, hi = rows * cols - 1;
  while (lo <= hi) {
    const m = lo + ((hi - lo) >> 1), v = mat[(m / cols) | 0][m % cols];
    if (v === t) return true;
    if (v < t) lo = m + 1; else hi = m - 1;
  }
  return false;
}
assert.equal(searchMatrix([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 3), true);
assert.equal(searchMatrix([[1, 3, 5, 7], [10, 11, 16, 20], [23, 30, 34, 60]], 13), false);
assert.equal(searchMatrix([], 1), false);

// ── 12. sqrt(x) (integer floor)  —  largest m with m*m <= x; upper-bound style  —  O(log x)
function mySqrt(x) {
  let lo = 0, hi = x;
  while (lo < hi) {
    const m = lo + ((hi - lo + 1) >> 1); // bias up when searching for the LAST true
    if (m * m <= x) lo = m; else hi = m - 1;
  }
  return lo;
}
assert.equal(mySqrt(8), 2);
assert.equal(mySqrt(16), 4);
assert.equal(mySqrt(0), 0);

console.log('ok: algorithms/binary-search.js');