Implementing Modified Binary Search

1. Understanding Search Space Reduction

Concept	Description	Key Insight
Search Space	The set of all possible solutions or elements to consider during a search	Reducing the search space efficiently is the core goal of modified binary search
Reduction Strategy	Eliminating half of the remaining elements at each step based on comparison logic	Effective reduction leads to O(log n) time complexity
Variants	Rotated arrays, mountain arrays, peak finding, order-agnostic search	Each variant modifies the comparison condition to achieve space reduction

Example: Finding Peak in Mountain Array

function findPeak(arr) {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] < arr[mid + 1]) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return left;
}

// Example usage:
const mountain = [1, 3, 5, 4, 2];
console.log(findPeak(mountain)); // Output: 2 (index of peak element)

Note: The key insight is that at any point, if the element at mid is less than its right neighbor, we know the peak must lie to the right. Otherwise, it lies to the left or is at mid.

2. Finding Minimum Capacity to Ship Packages

Given a list of packages and a number of days to ship them, find the minimum weight capacity of the ship required to ship all packages within the given days.

Parameter	Description	Example Value
weights	Array of package weights	`[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]`
days	Number of days to ship all packages	`5`

Example: Finding Minimum Capacity

function shipWithinDays(weights, days) {
    let left = Math.max(...weights);
    let right = weights.reduce((a, b) => a + b, 0);
    
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        let needDays = 1;
        let currentWeight = 0;
        
        for (let weight of weights) {
            if (currentWeight + weight > mid) {
                needDays++;
                currentWeight = 0;
            }
            currentWeight += weight;
        }
        
        if (needDays <= days) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
}

// Example usage:
const weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const days = 5;
console.log(shipWithinDays(weights, days)); // Output: 15

Note: This problem uses binary search on the answer space, where the search space is between the maximum weight of a single package and the total weight of all packages.

3. Finding Smallest Divisor

Property	Description	Example
Algorithm	Finds the smallest divisor of a number greater than 1	`smallestDivisor(12) = 2`
Time Complexity	O(√n)	Iterates up to square root of n
Space Complexity	O(1)	Uses constant space

Example: Finding Smallest Divisor

function smallestDivisor(n) {
  if (n <= 1) return null;
  for (let i = 2; i * i <= n; i++) {
    if (n % i === 0) return i;
  }
  return n;
}

// Example usage:
console.log(smallestDivisor(12)); // Output: 2
console.log(smallestDivisor(17)); // Output: 17 (prime)

Note: For prime numbers, the smallest divisor is the number itself.

4. Finding Minimum Eating Speed

Given a list of piles of bananas and the number of hours available, determine the minimum eating speed (bananas per hour) such that all bananas can be eaten within the given time.

Parameter	Description	Values
piles	Array of banana piles	`[3, 6, 7, 11]`
h	Hours available to eat all bananas	`8`

Example: Calculate Minimum Eating Speed

function minEatingSpeed(piles, h) {
    let left = 1;
    let right = Math.max(...piles);
    
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        let hours = 0;
        
        for (let pile of piles) {
            hours += Math.ceil(pile / mid);
        }
        
        if (hours <= h) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    
    return left;
}

// Example usage:
const piles = [3, 6, 7, 11];
const h = 8;
console.log(minEatingSpeed(piles, h)); // Output: 4

Note: The solution uses binary search on the eating speed, where the lower bound is 1 and the upper bound is the maximum pile size. For each mid value, calculate the total hours needed to eat all piles at that speed and adjust the search space accordingly.

5. Finding Minimum Days for Bouquets

Given a list of bloom days for flowers and the number of bouquets to make, find the minimum number of days required to make all bouquets.

Parameter	Description	Values
bloomDays	Array of integers representing the days each flower blooms	`[1, 2, 3, 4, 5]`
m	Number of bouquets to make	`2`
k	Number of adjacent flowers needed to make one bouquet	`3`

Example: Finding Minimum Days for Bouquets

function minDays(bloomDays, m, k) {
    if (m * k > bloomDays.length) return -1;

    let left = 1;
    let right = Math.max(...bloomDays);

    function canMakeBouquets(days) {
        let bouquets = 0;
        let consecutive = 0;

        for (let i = 0; i < bloomDays.length; i++) {
            if (bloomDays[i] <= days) {
                consecutive++;
                if (consecutive === k) {
                    bouquets++;
                    consecutive = 0;
                }
            } else {
                consecutive = 0;
            }
        }

        return bouquets >= m;
    }

    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (canMakeBouquets(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return left;
}

// Example usage:
const bloomDays = [1, 2, 3, 4, 5];
const m = 2;
const k = 3;
console.log(minDays(bloomDays, m, k)); // Output: 4

Note: This algorithm uses binary search on the answer space to find the minimum number of days required to make all bouquets.

6. Splitting Array with Largest Sum

This pattern involves dividing an array into subarrays such that the maximum sum among all subarrays is minimized. It's a classic application of binary search on the answer.

Property	Description	Notes
Array	Input array of integers	Must be non-empty and contain only positive integers
k	Number of subarrays to split into	Must be between 1 and array length
Max Sum	Minimum possible largest sum of any subarray	Target value to minimize

Example: Splitting Array to Minimize Largest Sum

function splitArray(nums, k) {
    let left = Math.max(...nums);
    let right = nums.reduce((a, b) => a + b, 0);

    function canSplit(maxSum) {
        let splits = 1;
        let currentSum = 0;

        for (let num of nums) {
            if (currentSum + num > maxSum) {
                splits++;
                currentSum = num;
            } else {
                currentSum += num;
            }
        }

        return splits <= k;
    }

    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (canSplit(mid)) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    return left;
}

// Example usage:
const nums = [7, 2, 5, 10, 8];
const k = 2;
console.log(splitArray(nums, k)); // Output: 18

Note: The algorithm uses binary search on the possible values of the maximum sum. For each candidate value, it checks if it's possible to split the array into at most k subarrays such that no subarray has a sum greater than this value.

7. Finding Minimum Time for Tasks

Property	Description	Usage
tasks	List of tasks with their durations	Array of integers representing time required for each task
workers	Number of workers available	Integer indicating how many concurrent workers are available
minTime	Minimum time to complete all tasks	Calculated using binary search over possible time values

Example: Finding Minimum Time for Tasks

function findMinTime(tasks, workers) {
  let left = Math.max(...tasks);
  let right = tasks.reduce((sum, task) => sum + task, 0);
  
  function canComplete(timeLimit) {
    let workersNeeded = 1;
    let currentLoad = 0;
    
    for (let task of tasks) {
      if (task > timeLimit) return false;
      if (currentLoad + task <= timeLimit) {
        currentLoad += task;
      } else {
        workersNeeded++;
        currentLoad = task;
      }
    }
    
    return workersNeeded <= workers;
  }
  
  while (left < right) {
    let mid = Math.floor((left + right) / 2);
    if (canComplete(mid)) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
  
  return left;
}

// Example usage:
const tasks = [3, 2, 3];
const workers = 3;
console.log(findMinTime(tasks, workers)); // Output: 3

Note: This algorithm uses binary search to find the minimum time required to complete all tasks with a given number of workers. It checks if a certain time limit allows completion of all tasks within the worker count.

8. Finding Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays. The overall run time complexity should be O(log(m + n)).

Property	Description	Notes
Input	Two sorted arrays `nums1` and `nums2`	Arrays can be of different sizes
Output	Median value of merged array	Can be a float if total length is even
Time Complexity	`O(log(min(m, n)))`	Using binary search on the smaller array

Example:

function findMedianSortedArrays(nums1, nums2) {
    if (nums1.length > nums2.length) {
        [nums1, nums2] = [nums2, nums1];
    }

    let left = 0;
    let right = nums1.length;

    while (left <= right) {
        const partition1 = Math.floor((left + right) / 2);
        const partition2 = Math.floor((nums1.length + nums2.length + 1) / 2) - partition1;

        const maxLeft1 = (partition1 === 0) ? Number.NEGATIVE_INFINITY : nums1[partition1 - 1];
        const minRight1 = (partition1 === nums1.length) ? Number.POSITIVE_INFINITY : nums1[partition1];

        const maxLeft2 = (partition2 === 0) ? Number.NEGATIVE_INFINITY : nums2[partition2 - 1];
        const minRight2 = (partition2 === nums2.length) ? Number.POSITIVE_INFINITY : nums2[partition2];

        if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
            const total = nums1.length + nums2.length;
            if (total % 2 === 0) {
                return (Math.max(maxLeft1, maxLeft2) + Math.min(minRight1, minRight2)) / 2;
            } else {
                return Math.max(maxLeft1, maxLeft2);
            }
        } else if (maxLeft1 > minRight2) {
            right = partition1 - 1;
        } else {
            left = partition1 + 1;
        }
    }

    throw new Error("Input arrays are not sorted");
}

// Example usage:
const nums1 = [1, 3];
const nums2 = [2];
console.log(findMedianSortedArrays(nums1, nums2)); // Output: 2.0

Note: The algorithm uses binary search to partition the arrays such that elements on the left are less than or equal to elements on the right in both arrays.

9. Finding Kth Element in Sorted Matrix

Given a matrix where each row and column is sorted in ascending order, find the kth smallest element in the matrix.

Approach	Description	Time Complexity	Space Complexity
Binary Search on Values	Use binary search on the value range to count elements less than or equal to a mid value	`O(log(max - min) * n * log n)`	`O(1)`
Min-Heap	Use a min-heap to keep track of the smallest elements and extract k times	`O(n^2 * log n)`	`O(n)`

Example: Binary Search on Values

function kthSmallest(matrix, k) {
    const n = matrix.length;
    let left = matrix[0][0];
    let right = matrix[n - 1][n - 1];

    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        let count = 0;
        let max = matrix[0][0];

        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                if (matrix[i][j] <= mid) {
                    count++;
                    max = Math.max(max, matrix[i][j]);
                } else {
                    break;
                }
            }
        }

        if (count < k) {
            left = max;
        } else {
            right = mid;
        }
    }

    return left;
}

// Example usage:
const matrix = [
  [1,  5,  9],
  [10, 11, 13],
  [12, 13, 15]
];
console.log(kthSmallest(matrix, 8)); // Output: 13

Example: Min-Heap Approach

function kthSmallest(matrix, k) {
    const minHeap = new MinHeap();
    const n = matrix.length;

    // Insert first element of each row
    for (let i = 0; i < n; i++) {
        minHeap.push({
            value: matrix[i][0],
            row: i,
            col: 0
        });
    }

    let result = 0;
    for (let i = 0; i < k; i++) {
        const current = minHeap.pop();
        result = current.value;

        if (current.col + 1 < n) {
            minHeap.push({
                value: matrix[current.row][current.col + 1],
                row: current.row,
                col: current.col + 1
            });
        }
    }

    return result;
}

class MinHeap {
    constructor() {
        this.heap = [];
    }

    push(val) {
        this.heap.push(val);
        this.bubbleUp(this.heap.length - 1);
    }

    pop() {
        if (this.heap.length === 0) return null;
        if (this.heap.length === 1) return this.heap.pop();

        const min = this.heap[0];
        this.heap[0] = this.heap.pop();
        this.bubbleDown(0);
        return min;
    }

    bubbleUp(index) {
        if (index === 0) return;
        const parentIndex = Math.floor((index - 1) / 2);
        if (this.heap[parentIndex].value > this.heap[index].value) {
            [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
            this.bubbleUp(parentIndex);
        }
    }

    bubbleDown(index) {
        const leftChild = 2 * index + 1;
        const rightChild = 2 * index + 2;
        let minIndex = index;

        if (leftChild < this.heap.length && this.heap[leftChild].value < this.heap[minIndex].value) {
            minIndex = leftChild;
        }

        if (rightChild < this.heap.length && this.heap[rightChild].value < this.heap[minIndex].value) {
            minIndex = rightChild;
        }

        if (minIndex !== index) {
            [this.heap[index], this.heap[minIndex]] = [this.heap[minIndex], this.heap[index]];
            this.bubbleDown(minIndex);
        }
    }
}

// Example usage:
const matrix = [
  [1,  5,  9],
  [10, 11, 13],
  [12, 13, 15]
];
console.log(kthSmallest(matrix, 8)); // Output: 13

10. Finding Minimum in Rotated Array with Duplicates

Property	Description	Notes
Input	Rotated sorted array with possible duplicates	Array is sorted in ascending order and then rotated at some pivot
Output	Minimum element in the array	Element that is smallest in value
Time Complexity	O(log n) average, O(n) worst case	Worst case occurs when all elements are the same
Space Complexity	O(1)	Constant space usage

Example: Finding Minimum in Rotated Array with Duplicates

function findMinInRotatedWithDuplicates(nums) {
    let left = 0;
    let right = nums.length - 1;

    while (left < right) {
        const mid = Math.floor((left + right) / 2);

        if (nums[mid] > nums[right]) {
            left = mid + 1;
        } else if (nums[mid] < nums[right]) {
            right = mid;
        } else {
            right--;
        }
    }

    return nums[left];
}

// Example usage:
const arr1 = [3, 4, 5, 1, 2];
console.log(findMinInRotatedWithDuplicates(arr1)); // Output: 1

const arr2 = [2, 2, 2, 0, 1];
console.log(findMinInRotatedWithDuplicates(arr2)); // Output: 0

const arr3 = [1, 1, 1, 1];
console.log(findMinInRotatedWithDuplicates(arr3)); // Output: 1

Note: When nums[mid] === nums[right], we can't determine which half contains the minimum, so we reduce the search space by decrementing right.