Binary Search Applications

// Template for Binary Search on Answer Space
function binarySearchOnAnswer(
    minPossible: number,
    maxPossible: number,
    isValidAnswer: (candidate: number) => boolean,
    findMinimum: boolean = true
): number {
    let left = minPossible;
    let right = maxPossible;
    let result = findMinimum ? maxPossible : minPossible;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (isValidAnswer(mid)) {
            result = mid;
            if (findMinimum) {
                right = mid - 1; // Look for smaller valid answer
            } else {
                left = mid + 1;  // Look for larger valid answer
            }
        } else {
            if (findMinimum) {
                left = mid + 1;  // Need larger value
            } else {
                right = mid - 1; // Need smaller value
            }
        }
    }
    
    return result;
}

// 1. Koko Eating Bananas
function minEatingSpeed(piles: number[], h: number): number {
    const maxPile = Math.max(...piles);
    
    // Can we finish all bananas in h hours with speed k?
    const canFinish = (k: number): boolean => {
        let hoursNeeded = 0;
        for (const pile of piles) {
            hoursNeeded += Math.ceil(pile / k);
        }
        return hoursNeeded <= h;
    };
    
    return binarySearchOnAnswer(1, maxPile, canFinish, true);
}

// 2. Capacity to Ship Packages Within D Days
function shipWithinDays(weights: number[], days: number): number {
    const minCapacity = Math.max(...weights);
    const maxCapacity = weights.reduce((sum, w) => sum + w, 0);
    
    // Can we ship all packages in days with capacity?
    const canShip = (capacity: number): boolean => {
        let daysNeeded = 1;
        let currentWeight = 0;
        
        for (const weight of weights) {
            if (currentWeight + weight > capacity) {
                daysNeeded++;
                currentWeight = weight;
            } else {
                currentWeight += weight;
            }
        }
        
        return daysNeeded <= days;
    };
    
    return binarySearchOnAnswer(minCapacity, maxCapacity, canShip, true);
}

// 3. Split Array Largest Sum
function splitArray(nums: number[], k: number): number {
    const minSum = Math.max(...nums);
    const maxSum = nums.reduce((sum, num) => sum + num, 0);
    
    // Can we split array into k subarrays with max sum <= target?
    const canSplit = (target: number): boolean => {
        let subarrays = 1;
        let currentSum = 0;
        
        for (const num of nums) {
            if (currentSum + num > target) {
                subarrays++;
                currentSum = num;
            } else {
                currentSum += num;
            }
        }
        
        return subarrays <= k;
    };
    
    return binarySearchOnAnswer(minSum, maxSum, canSplit, true);
}

// 4. Find Kth Smallest in Multiplication Table
function findKthNumber(m: number, n: number, k: number): number {
    // Count how many numbers <= x in multiplication table
    const countLessEqual = (x: number): number => {
        let count = 0;
        for (let i = 1; i <= m; i++) {
            count += Math.min(Math.floor(x / i), n);
        }
        return count;
    };
    
    // Is x >= kth smallest number?
    const isKthOrLarger = (x: number): boolean => {
        return countLessEqual(x) >= k;
    };
    
    return binarySearchOnAnswer(1, m * n, isKthOrLarger, true);
}

// 5. Minimum Number of Days to Make m Bouquets
function minDays(bloomDay: number[], m: number, k: number): number {
    if (m * k > bloomDay.length) return -1;
    
    const minDay = Math.min(...bloomDay);
    const maxDay = Math.max(...bloomDay);
    
    // Can we make m bouquets by day d?
    const canMakeBouquets = (day: number): boolean => {
        let bouquets = 0;
        let consecutive = 0;
        
        for (const bloom of bloomDay) {
            if (bloom <= day) {
                consecutive++;
                if (consecutive === k) {
                    bouquets++;
                    consecutive = 0;
                }
            } else {
                consecutive = 0;
            }
        }
        
        return bouquets >= m;
    };
    
    const result = binarySearchOnAnswer(minDay, maxDay, canMakeBouquets, true);
    return result === maxDay + 1 ? -1 : result;
}

// Example usage
function demonstrateAnswerSpaceSearch(): void {
    console.log("Koko Eating Bananas:");
    console.log(minEatingSpeed([3,6,7,11], 8)); // 4
    
    console.log("\nShip Within Days:");
    console.log(shipWithinDays([1,2,3,4,5,6,7,8,9,10], 5)); // 15
    
    console.log("\nSplit Array Largest Sum:");
    console.log(splitArray([7,2,5,10,8], 2)); // 18
}
                                

// 1. Minimize Maximum - Painter's Partition Problem
function paintersPartition(boards: number[], painters: number): number {
    const minTime = Math.max(...boards);
    const maxTime = boards.reduce((sum, board) => sum + board, 0);
    
    // Can we paint all boards with painters in time?
    const canPaint = (time: number): boolean => {
        let paintersUsed = 1;
        let currentTime = 0;
        
        for (const board of boards) {
            if (currentTime + board > time) {
                paintersUsed++;
                currentTime = board;
            } else {
                currentTime += board;
            }
        }
        
        return paintersUsed <= painters;
    };
    
    return binarySearchOnAnswer(minTime, maxTime, canPaint, true);
}

// 2. Maximize Minimum - Aggressive Cows
function aggressiveCows(stalls: number[], cows: number): number {
    stalls.sort((a, b) => a - b);
    const minDistance = 1;
    const maxDistance = stalls[stalls.length - 1] - stalls[0];
    
    // Can we place cows with minimum distance d?
    const canPlaceCows = (distance: number): boolean => {
        let placed = 1;
        let lastPosition = stalls[0];
        
        for (let i = 1; i < stalls.length; i++) {
            if (stalls[i] - lastPosition >= distance) {
                placed++;
                lastPosition = stalls[i];
                if (placed === cows) return true;
            }
        }
        
        return false;
    };
    
    return binarySearchOnAnswer(minDistance, maxDistance, canPlaceCows, false);
}

// 3. Book Allocation Problem
function allocateBooks(books: number[], students: number): number {
    if (students > books.length) return -1;
    
    const minPages = Math.max(...books);
    const maxPages = books.reduce((sum, pages) => sum + pages, 0);
    
    // Can we allocate books such that max pages <= limit?
    const canAllocate = (limit: number): boolean => {
        let studentsUsed = 1;
        let currentPages = 0;
        
        for (const pageCount of books) {
            if (currentPages + pageCount > limit) {
                studentsUsed++;
                currentPages = pageCount;
            } else {
                currentPages += pageCount;
            }
        }
        
        return studentsUsed <= students;
    };
    
    return binarySearchOnAnswer(minPages, maxPages, canAllocate, true);
}

// 4. Minimum Speed to Arrive on Time
function minSpeedOnTime(dist: number[], hour: number): number {
    const n = dist.length;
    
    // Need at least n-1 hours for n-1 trains + some time for last train
    if (hour <= n - 1) return -1;
    
    const maxSpeed = 10000000; // Given constraint
    
    // Can we reach on time with speed s?
    const canReachOnTime = (speed: number): boolean => {
        let totalTime = 0;
        
        // First n-1 trains: need integer hours (ceiling)
        for (let i = 0; i < n - 1; i++) {
            totalTime += Math.ceil(dist[i] / speed);
        }
        
        // Last train: can use fractional time
        totalTime += dist[n - 1] / speed;
        
        return totalTime <= hour;
    };
    
    const result = binarySearchOnAnswer(1, maxSpeed, canReachOnTime, true);
    return result > maxSpeed ? -1 : result;
}

// 5. Cutting Ribbons
function maxLength(ribbons: number[], k: number): number {
    if (k === 0) return 0;
    
    const maxRibbon = Math.max(...ribbons);
    
    // Can we cut k pieces of length len?
    const canCut = (length: number): boolean => {
        let pieces = 0;
        for (const ribbon of ribbons) {
            pieces += Math.floor(ribbon / length);
            if (pieces >= k) return true;
        }
        return false;
    };
    
    return binarySearchOnAnswer(1, maxRibbon, canCut, false);
}

// Example usage
function demonstrateOptimization(): void {
    console.log("Painter's Partition:");
    console.log(paintersPartition([10, 20, 30, 40], 2)); // 60
    
    console.log("\nAggressive Cows:");
    console.log(aggressiveCows([1, 2, 4, 8, 9], 3)); // 3
    
    console.log("\nBook Allocation:");
    console.log(allocateBooks([12, 34, 67, 90], 2)); // 113
}