Binary Search (and Variants)

Binary Search (and Variants)

Problem Scenario / Typical Use Case

Imagine you are managing an online inventory system, and you need to quickly check whether a product with a certain price exists among thousands of sorted items.

Scanning sequentially is inefficient. The Binary Search pattern leverages the sorted order of data to drastically reduce search time by repeatedly halving the search space.

Basic Idea

Binary Search involves:

1. Divide: Identify the middle element of the current search interval.
2. Compare: If it matches the target, return it; otherwise, determine which half of the interval may contain the target.
3. Repeat: Continue searching recursively or iteratively on the selected half until the element is found or the interval is empty.

Variants include:

• Lower/Upper Bound Search: Find the first/last occurrence of a value.
• Search in Rotated Arrays: Adjust comparisons to handle rotations.
• Binary Search on Answer: Use binary search to find the smallest/largest value that satisfies a condition.

Advantages

• Efficiency: Reduces search complexity from (O(n)) to (O(\log n)).
• Predictability: Deterministic and reliable for sorted datasets.
• Versatility: Can be applied beyond arrays, e.g., on monotonic functions or decision spaces.

Limitations / Considerations

• Only works on sorted or monotonic datasets.
• Requires careful handling of mid calculation and boundary conditions to avoid infinite loops or off-by-one errors.
• Recursive variants may hit stack limits for very deep searches.

Practical Examples / Thought Triggers

1. Search a Product in Sorted Inventory: Quickly locate a specific price or SKU.
2. First/Last Occurrence of an Element: Use lower/upper bound variants for duplicate elements.
3. Optimizing Resource Allocation: Binary Search on Answer to find the minimal required capacity to satisfy constraints.

Thought Triggers:

• Is the data fully sorted, or is it rotated or partially monotonic?
• Should I use iterative or recursive implementation for clarity and stack safety?
• Can I combine this with other patterns like Two Pointers or Sliding Window for range-based searches?

Implementation Example

Here’s a Python example for classic binary search:

def binary_search(arr, target):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return -1  # Not found

# Example usage
inventory_prices = [10, 20, 30, 40, 50]
print(binary_search(inventory_prices, 30))
# Output: 2

This demonstrates the core principle: halving the search space efficiently until the target is found.

Related Articles

• Divide & Conquer: Binary Search is a classic example of this principle.
• Two Pointers: Can be combined for problems like search in sorted 2D matrices.
• Sliding Window: In some cases, binary search can be applied to determine optimal window sizes.