Binary Search Algorithms

Binary search can be categorized into three main types:

1. Exact Value or Classic
2. Range or Boundary
3. Search in Constrained Space

---

1. Exact Value or Classic

This is the traditional binary search for finding a specific value in a sorted array. The algorithm uses three branches:

• Check if mid is the solution (e.g., nums[mid] == target).
• If nums[mid] < target, adjust l = mid + 1.
• If nums[mid] > target, adjust r = mid - 1.

Example:

def binary_search(nums, target):
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] == target:
            return mid  # Found exact match
        elif nums[mid] < target:
            l = mid + 1  # Search right
        else:
            r = mid - 1  # Search left
    return -1  # Target not found

---

2. Range or Boundary

This type of binary search does not look for an exact match but instead finds a boundary:

• The smallest value satisfying a condition (e.g., nums[mid] >= target).
• The largest value satisfying a condition (e.g., nums[mid] <= target).

Example: Find First Occurrence

def find_first_occurrence(nums, target):
    l, r = 0, len(nums) - 1
    result = -1
    while l <= r:
        mid = (l + r) // 2
        if nums[mid] >= target:  # Check left boundary
            if nums[mid] == target:
                result = mid  # Store potential result
            r = mid - 1  # Narrow to left side
        else:
            l = mid + 1  # Narrow to right side
    return result

CDF Use Case (Smallest Index Where CDF[i] >= target)

For weighted sampling problems, the prefix sum is the cumulative distribution function (CDF). Binary search finds the smallest index satisfying a probability condition.

def find_cdf_index(cdf, target):
    l, r = 0, len(cdf) - 1
    while l < r:  # Use `l < r` to find smallest index
        mid = (l + r) // 2
        if cdf[mid] >= target:
            r = mid  # Keep searching left
        else:
            l = mid + 1  # Move right
    return l

Tip: Use l < r to avoid skipping valid candidates when searching for boundaries. This ensures the search converges correctly.

---

3. Search in Constrained Space

This type of binary search is used when searching for the optimal value in a range, such as:

• Finding the minimum capacity to meet a constraint.
• Finding the maximum load a system can handle.
• Finding the k-th smallest value in a dataset.

The search space here is a range of possible values, not array indices.

Example: Minimum Capacity to Ship Packages

def min_capacity(weights, days):
    def can_ship(capacity):
        current_weight = 0
        days_needed = 1
        for weight in weights:
            if current_weight + weight > capacity:
                days_needed += 1
                current_weight = 0
            current_weight += weight
        return days_needed <= days
 
    l, r = max(weights), sum(weights)  # Search space: max(weights) to sum(weights)
    while l < r:
        mid = (l + r) // 2
        if can_ship(mid):  # Check if capacity is sufficient
            r = mid  # Try smaller capacity
        else:
            l = mid + 1  # Try larger capacity
    return l

---

Summary Table

Type	Use Case	Adjustment
Exact Value	Find a specific value	l = mid + 1, r = mid - 1
Range or Boundary	Find smallest/largest satisfying condition	r = mid, l = mid + 1
Constrained Space	Search for optimal value in a range	Based on condition evaluation