Pattern 06: Binary Search & Binary Search on Answer

Binary Search is an optimal divide-and-conquer algorithmic technique designed to locate a target element, find a boundary condition, or solve an optimization problem in $O(\log N)$ time complexity. By leveraging sorted order or monotonic feasibility properties, the algorithm repeatedly halves the candidate search space, serving as an intelligent alternative to linear brute-force evaluation.

1. Core Mental Model & The Power of Halving

In a standard linear search over an array of size $N$, every element must be inspected sequentially in the worst-case scenario, yielding a time complexity of $O(N)$.

When data exhibits a monotonic relationship (such as being strictly sorted in ascending or descending order), we do not need to evaluate elements one by one. By probing the middle element ($\text{mid}$), we can determine with certainty whether the target resides in the left half or the right half of the search interval.

The Mathematics of Logarithmic Time

With each iteration, the remaining search window is halved:

Setting $\frac{N}{2^k} = 1$ yields:

Thus, the algorithm terminates in at most $\lceil \log_2 N \rceil$ iterations, making it exceptionally fast even for massive data inputs (e.g., searching $10^9$ elements takes only $\approx 30$ operations).

2. Anatomy and Pattern Recognition Framework

Binary search extends beyond looking up numbers in a standard sorted list. It applies to any problem that maps to a monotonic decision space.

Monotonic Feasibility Function

For optimization problems ("Binary Search on Answer"), the domain can be modeled as a boolean predicate that transitions monotonically from false to true (or vice versa):

Capacity / Parameter X:   10    11    12    13    14    15    16    17
Feasible within D days? [ F  ,  F  ,  F  ,  F  ,  F  ,  T  ,  T  ,  T  ]
                                                        ^
                                               First True (Optimal Min)

Whenever a problem asks for:

• The minimum capacity to finish within $D$ days
• The maximum threshold that satisfies a resource constraint
• The first/last position where an event occurs

...the search space is monotonic, and Binary Search is applicable.

3. Template 1: Classic 1D Binary Search

Given a sorted integer array nums and an integer target, return the index of target if found; otherwise, return -1.

Safe Midpoint Calculation

Using (low + high) / 2 can cause integer overflow in languages with fixed-width integers (like Java/C++) when $\text{low} + \text{high} > 2^{31} - 1$.

To avoid overflow, compute mid as:

Implementation (Java)

public class BinarySearch1D {
    public int search(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (nums[mid] == target) {
                return mid; // Target discovered
            } else if (target < nums[mid]) {
                high = mid - 1; // Discard right half
            } else {
                low = mid + 1;  // Discard left half
            }
        }

        return -1; // Target does not exist
    }
}

• Time Complexity: $O(\log N)$
• Space Complexity: $O(1)$ in-place

4. Template 2: Search in a 2D Matrix (Virtual Flattening)

When a 2D matrix of dimensions $M \times N$ satisfies two properties:

1. Each row is sorted in ascending order.
2. The first integer of each row is strictly greater than the last integer of the previous row.

The entire 2D matrix can be treated as a single continuous 1D sorted array of size $M \times N$.

Matrix (3 x 4):
Row 0: [  1,   3,   5,   7 ]
Row 1: [ 10,  11,  16,  20 ]
Row 2: [ 23,  30,  34,  60 ]

Conceptual 1D Flattening:
Index:   0   1   2   3   4   5   6   7   8   9  10  11
Value: [ 1,  3,  5,  7, 10, 11, 16, 20, 23, 30, 34, 60 ]

Coordinate Mapping Math

Instead of copying elements into an auxiliary array (which takes $O(M \times N)$ space), map a 1D index mid back to its 2D coordinates (row, col) in $O(1)$ time:

Where $N$ is the number of columns (matrix[0].length).

Implementation (Java)

public class Search2DMatrix {
    public boolean searchMatrix(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }

        int m = matrix.length;
        int n = matrix[0].length;
        
        int low = 0;
        int high = (m * n) - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            
            // Map 1D index to 2D matrix indices
            int row = mid / n;
            int col = mid % n;
            int midValue = matrix[row][col];

            if (midValue == target) {
                return true;
            } else if (target < midValue) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return false;
    }
}

• Time Complexity: $O(\log(M \times N))$
• Space Complexity: $O(1)$

5. Template 3: Search in Rotated Sorted Array

An array sorted in ascending order with distinct values is rotated at an unknown pivot index $k$.

Original Array: [ 0, 1, 2, 4, 5, 6, 7 ]
Rotated Array:  [ 4, 5, 6, 7, 0, 1, 2 ]
                             ^
                           Pivot

The Invariant: One Half is Always Sorted

When splitting a rotated sorted array at any arbitrary mid, at least one half (left or right) remains normally sorted.

Case A: Left Half is Sorted (nums[low] <= nums[mid])
[ 4,  5,  6,  7,  0,  1,  2 ]
  ^           ^
 low         mid
Since 4 <= 7: Left sub-array [4, 5, 6, 7] is strictly sorted.

Case B: Right Half is Sorted (nums[low] > nums[mid])
[ 6,  7,  0,  1,  2,  4,  5 ]
  ^           ^
 low         mid
Since 6 > 1: Right sub-array [1, 2, 4, 5] is strictly sorted.

Decision Logic Workflow

Implementation (Java)

public class RotatedSortedSearch {
    public int search(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;

        while (low <= high) {
            int mid = low + (high - low) / 2;

            if (nums[mid] == target) {
                return mid;
            }

            // Check if left half is normally sorted
            if (nums[low] <= nums[mid]) {
                // Check if target lies within the sorted left half
                if (nums[low] <= target && target < nums[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            } 
            // Otherwise, right half must be sorted
            else {
                // Check if target lies within the sorted right half
                if (nums[mid] < target && target <= nums[high]) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
        }

        return -1;
    }
}

• Time Complexity: $O(\log N)$
• Space Complexity: $O(1)$

6. Template 4: Binary Search on Answer (Optimization Problems)

When the problem asks for the minimum or maximum value $X$ satisfying a specific condition, we perform binary search over the range of possible answers rather than array indices.

7. Deep Dive: Capacity to Ship Packages Within D Days

Problem Breakdown

• Given an array weights representing parcel weights in order of delivery, and an integer days.
• Find the minimum ship weight capacity required to ship all packages within days.
• Packages must be loaded in the exact order given.

Defining Search Range Boundaries

Lower Bound (low):
Must be at least max(weights) = 10
(If capacity < 10, the heaviest package of weight 10 could never be shipped).

Upper Bound (high):
Must be at most sum(weights) = 55
(If capacity = 55, all packages ship in exactly 1 day).

Search Range: [ 10, 55 ]

Complete Implementation with Feasibility Helper (Java)

public class ShipWithinDays {
    public int shipWithinDays(int[] weights, int days) {
        int low = 0;
        int high = 0;

        for (int w : weights) {
            low = Math.max(low, w); // Max single element
            high += w;              // Sum of all elements
        }

        while (low < high) {
            int mid = low + (high - low) / 2;

            if (canShip(weights, days, mid)) {
                // mid is feasible; try to find a smaller feasible capacity on the left
                high = mid;
            } else {
                // mid is too small; must increase capacity
                low = mid + 1;
            }
        }

        return low; // Optimal minimum capacity
    }

    // Greedy helper to check if capacity can ship within specified days
    private boolean canShip(int[] weights, int daysLimit, int capacity) {
        int daysUsed = 1;
        int currentLoad = 0;

        for (int w : weights) {
            if (currentLoad + w > capacity) {
                daysUsed++;
                currentLoad = 0;
            }
            currentLoad += w;

            if (daysUsed > daysLimit) {
                return false; // Exceeded allowed days
            }
        }

        return true;
    }
}

Dry Run Trace

Let weights = [3, 2, 2, 4, 1, 4], days = 3:

• low = max(weights) = 4
• high = sum(weights) = 16

• Time Complexity: $O(N \cdot \log(\sum W - \max(W)))$ where $N$ is the length of weights.
• Space Complexity: $O(1)$ auxiliary memory.

8. Common Pitfalls & Edge Case Analysis

1. Loop Condition: while (low <= high) vs while (low < high)

• low <= high (Standard Index Search): Used when searching for an exact target value where matching nums[mid] == target immediately returns. high = mid - 1 and low = mid + 1 guarantee convergence.
• low < high (Boundary / Min-Value Search): Used when mid itself could be the answer (high = mid). The loop terminates when low == high, pointing directly to the optimal boundary without infinite looping.

2. Setting high = mid - 1 vs high = mid in Optimization Problems

Note: In optimization problems where canShip(mid) == true, mid is a valid candidate. Setting high = mid - 1 would permanently discard that valid answer. Thus, keep high = mid.

3. Missing low = Math.max(weights)

If the ship's capacity is lower than the single largest item, that item can never be loaded onto the ship, leading to an infinite loop in the greedy validation subroutine.

9. Complexity & Pattern Comparison Matrix

10. Summary and Key Takeaways

• Halving Strategy: Binary Search reduces the search space by half at each step, scaling at logarithmic time $O(\log N)$.
• Preconditions: It requires either an explicitly sorted data structure or a monotonic feasibility predicate ($F \to T$).
• Overflow Prevention: Always calculate the midpoint using mid = low + (high - low) / 2.
• 2D Matrix Flattening: Convert conceptual 1D midpoints to 2D indices via row = mid / cols and col = mid % cols without extra space.
• Rotated Array Invariant: Any midpoint split in a rotated sorted array divides it into at least one normally sorted sub-array. Locate the sorted half first, then check whether the target lies within its boundaries.
• Binary Search on Answer: When an exact element lookup isn't provided, identify the minimum/maximum possible parameter bounds and perform binary search across candidate values using a helper validation function.
• Search Space Bounds for Packaging/Capacities: For partitioning problems, the lower search bound is always $\max(\text{items})$ and the upper bound is $\sum(\text{items})$.