17 — Binary Search Advanced

Binary Search Template

// Find first position where condition is true
function binarySearch(lo: number, hi: number, condition: (mid: number) => boolean): number {
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (condition(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

---

Search on Answer

When answer is a number in a range, binary search on the answer space.

Koko Eating Bananas

// Minimum eating speed to finish all piles in h hours
function minEatingSpeed(piles: number[], h: number): number {
  let lo = 1, hi = Math.max(...piles);
  
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    const hours = piles.reduce((sum, p) => sum + Math.ceil(p / mid), 0);
    if (hours <= h) hi = mid;   // Can eat slower
    else lo = mid + 1;          // Need to eat faster
  }
  return lo;
}

Split Array Largest Sum

// Split array into m subarrays, minimize the largest sum
function splitArray(nums: number[], m: number): number {
  let lo = Math.max(...nums);
  let hi = nums.reduce((a, b) => a + b);
  
  function canSplit(maxSum: number): boolean {
    let splits = 1, currentSum = 0;
    for (const num of nums) {
      if (currentSum + num > maxSum) { splits++; currentSum = 0; }
      currentSum += num;
    }
    return splits <= m;
  }
  
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (canSplit(mid)) hi = mid;
    else lo = mid + 1;
  }
  return lo;
}

---

Rotated Sorted Array

Search in Rotated Array

function search(nums: number[], target: number): number {
  let lo = 0, hi = nums.length - 1;
  
  while (lo <= hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid] === target) return mid;
    
    if (nums[lo] <= nums[mid]) {
      // Left half is sorted
      if (nums[lo] <= target && target < nums[mid]) hi = mid - 1;
      else lo = mid + 1;
    } else {
      // Right half is sorted
      if (nums[mid] < target && target <= nums[hi]) lo = mid + 1;
      else hi = mid - 1;
    }
  }
  return -1;
}

Find Minimum in Rotated Array

function findMin(nums: number[]): number {
  let lo = 0, hi = nums.length - 1;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid] > nums[hi]) lo = mid + 1;
    else hi = mid;
  }
  return nums[lo];
}

---

First / Last Occurrence

function firstOccurrence(nums: number[], target: number): number {
  let lo = 0, hi = nums.length;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid] < target) lo = mid + 1;
    else hi = mid;
  }
  return lo < nums.length && nums[lo] === target ? lo : -1;
}

function lastOccurrence(nums: number[], target: number): number {
  let lo = 0, hi = nums.length;
  while (lo < hi) {
    const mid = lo + ((hi - lo) >> 1);
    if (nums[mid] <= target) lo = mid + 1;
    else hi = mid;
  }
  return lo > 0 && nums[lo - 1] === target ? lo - 1 : -1;
}

---

Binary Search on Floating Point

// Square root with precision
function sqrt(x: number): number {
  let lo = 0, hi = x;
  for (let i = 0; i < 100; i++) { // ~100 iterations for high precision
    const mid = (lo + hi) / 2;
    if (mid * mid < x) lo = mid;
    else hi = mid;
  }
  return lo;
}

---

Search on Answer — Recognition

Clues:
  ✅ "Minimize the maximum..."
  ✅ "Maximize the minimum..."
  ✅ "Minimum speed/capacity/time to..."
  ✅ Answer has a monotonic feasibility function
  ✅ "Is it possible with value X?" → binary search on X

---

Key Takeaways

• Search on answer: binary search when feasibility is monotonic (once true, stays true)
• Rotated array: determine which half is sorted, then decide direction
• First/last occurrence: adjust lo/hi update logic (< target vs <= target)
• Use lo + ((hi - lo) >> 1) to avoid overflow
• Floating point binary search: fixed iterations instead of lo < hi