🔍 Binary Search

Concept

Binary Search repeatedly halves the search space by comparing the target to the middle element. It achieves O(log n) time on sorted data.

Beyond searching for a value, binary search can be applied to answer spaces — searching for a number that satisfies a condition (e.g., "minimum capacity", "k-th smallest").

---

When to Use

• Array is sorted (or rotated sorted)
• The problem asks for "minimum X such that condition holds" or "maximum X"
• Searching in an implicit sorted space (rope cutting, ship capacity, etc.)
• Finding boundaries (first occurrence, last occurrence)

---

Java Template

Classic: Find exact target

public int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2; // avoids overflow vs (left+right)/2
        if (nums[mid] == target) return mid;
        else if (nums[mid] < target) left = mid + 1;
        else right = mid - 1;
    }
    return -1; // not found
}

Find left boundary (first occurrence / leftmost valid)

public int leftBound(int[] nums, int target) {
    int left = 0, right = nums.length;
    while (left < right) {              // Note: right = length (exclusive)
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) left = mid + 1;
        else right = mid;               // do NOT do mid-1; we keep narrowing right
    }
    return left; // first index where nums[index] >= target
}

Find right boundary (last occurrence)

public int rightBound(int[] nums, int target) {
    int left = 0, right = nums.length;
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) left = mid + 1;
        else right = mid;
    }
    return left - 1; // last index where nums[index] <= target
}

Binary Search on Answer Space

// Template: find MINIMUM value x such that feasible(x) is true
public int binarySearchAnswer(int lo, int hi) {
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (feasible(mid)) hi = mid;       // mid might be the answer, keep it
        else lo = mid + 1;
    }
    return lo;
}

// feasible() implements the monotonic condition check

---

Worked Example 1: Search in Rotated Sorted Array

public int search(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;

        // Left half is sorted
        if (nums[left] <= nums[mid]) {
            if (nums[left] <= target && target < nums[mid]) right = mid - 1;
            else left = mid + 1;
        } else { // Right half is sorted
            if (nums[mid] < target && target <= nums[right]) left = mid + 1;
            else right = mid - 1;
        }
    }
    return -1;
}

---

Worked Example 2: Minimum Capacity to Ship Packages in D Days

Problem: Given weights[], find minimum ship capacity to ship all packages within days days.

public int shipWithinDays(int[] weights, int days) {
    // Minimum capacity = max single weight (must fit largest package)
    // Maximum capacity = total sum (ship everything in 1 day)
    int lo = Arrays.stream(weights).max().getAsInt();
    int hi = Arrays.stream(weights).sum();

    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (canShip(weights, days, mid)) hi = mid; // mid works, try smaller
        else lo = mid + 1;
    }
    return lo;
}

private boolean canShip(int[] weights, int days, int capacity) {
    int daysNeeded = 1, load = 0;
    for (int w : weights) {
        if (load + w > capacity) {
            daysNeeded++;
            load = 0;
        }
        load += w;
    }
    return daysNeeded <= days;
}

Time: O(n log(sum)) | Space: O(1)

---

LeetCode Problems

🟢 Easy

#	Problem	Variant
35	Search Insert Position	Left bound
69	Sqrt(x)	Answer space
278	First Bad Version	Left bound
374	Guess Number Higher or Lower	Classic
704	Binary Search	Classic

🟡 Medium

#	Problem	Variant
33	Search in Rotated Sorted Array	Rotated
34	Find First and Last Position	Left + Right bound
153	Find Minimum in Rotated Sorted Array	Rotated
162	Find Peak Element	Slope climbing
540	Single Element in Sorted Array	Parity check
875	Koko Eating Bananas	Answer space
1011	Capacity To Ship Packages	Answer space

🔴 Hard

#	Problem	Variant
4	Median of Two Sorted Arrays	Partition
410	Split Array Largest Sum	Answer space
668	Kth Smallest Number in Multiplication Table	Answer space