DSA: Binary Search Patterns

Solution to Last Week's Challenge

Last week's problem was: DSA: Stack-Based Problems

The optimal solution uses dsa: stack-based problems pattern with careful state management.

Complexity Analysis:

• Time Complexity: O(n)
• Space Complexity: O(1)

Binary search is often the first "advanced" algorithm engineers learn, yet it remains one of the most frequently failed topics in technical interviews. Its elegance lies in its efficiency; while a linear search through a billion elements takes a billion operations, binary search concludes in roughly thirty. In real-world systems, this logarithmic efficiency powers everything from database indexing (B-Trees) to version control systems like Git when performing a bisect to find a bug-introducing commit.

For a senior engineer, binary search is more than just a way to find a number in a sorted list. It is a powerful problem-solving template used whenever a search space is monotonic. Whether you are optimizing the memory allocation of a high-frequency trading system or determining the minimum throughput required for a distributed data pipeline, the ability to "search on the answer" using binary search is a critical architectural tool.

Theory and Core Concepts

The fundamental requirement for binary search is a monotonic relationship. This usually means the data is sorted, but more broadly, it means that if a condition is met for an index i, it is also met for all indices j > i (or vice versa). We maintain a search space defined by two pointers, low and high, and repeatedly narrow this space by half.

Complexity Analysis:

• Time Complexity: O(log n) because the search space is halved at each step.
• Space Complexity: O(1) for iterative implementations, or O(log n) for recursive implementations due to the call stack.

Pattern Visualization

The logic of binary search follows a strict decision-making process. The most critical part is defining the condition() function, which determines which half of the search space to discard.

Implementation

Let's look at the evolution from a naive search to an optimized binary search in Python.

Brute Force Approach (Linear Search)

def linear_search(nums, target):
    # Time: O(n), Space: O(1)
    for i in range(len(nums)):
        if nums[i] == target:
            return i
    return -1

Optimized Approach (Binary Search)

def binary_search(nums, target):
    # Time: O(log n), Space: O(1)
    low, high = 0, len(nums) - 1
    
    while low <= high:
        # Prevent overflow in languages like Java/C++
        mid = low + (high - low) // 2
        
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
            
    return -1

Complexity Analysis Table

Common Patterns

1. Finding the Leftmost Boundary

When duplicates exist, we often need the first occurrence.

def find_first(nums, target):
    low, high = 0, len(nums)
    while low < high:
        mid = low + (high - low) // 2
        if nums[mid] >= target:
            high = mid
        else:
            low = mid + 1
    return low

2. Search on Answer

This pattern is used when the "answer" exists within a range of values. For example, finding the minimum speed to finish a task.

def can_finish(speed, limit):
    # Logic to check if 'speed' is viable
    pass

def search_on_answer(low, high, limit):
    ans = high
    while low <= high:
        mid = low + (high - low) // 2
        if can_finish(mid, limit):
            ans = mid
            high = mid - 1
        else:
            low = mid + 1
    return ans

Practice Problems

To master these patterns, you should tackle problems across different difficulty levels. The following chart maps common LeetCode problems based on their interview frequency and conceptual difficulty.

This Week's Interview Challenge

Problem: The Efficient Cargo Loader

A conveyor belt carries packages that must be shipped within days days. The i-th package on the conveyor belt has a weight of weights[i]. Each day, we load the ship with packages in the order they appear on the belt. We cannot load more weight than the maximum weight capacity of the ship.

Return the least weight capacity of the ship that will result in all the packages on the conveyor belt being shipped within days days.

Example 1:

• Input: weights = [1,2,3,4,5,6,7,8,9,10], days = 5
• Output: 15
• Explanation: A ship capacity of 15 is the minimum to ship all packages in 5 days.

Example 2:

• Input: weights = [3,2,2,4,1,4], days = 3
• Output: 6

Constraints:

• 1 <= days <= weights.length <= 5 * 10^4
• 1 <= weights[i] <= 500

Hints:

1. What is the minimum possible capacity the ship must have? (It must be at least the weight of the heaviest package).
2. What is the maximum possible capacity? (The sum of all weights).
3. The capacity search space is monotonic. If a capacity X works, any capacity Y > X also works.
4. Use binary search to find the smallest capacity in the range [max(weights), sum(weights)].

Template Code:

def shipWithinDays(weights: list[int], days: int) -> int:
    def can_ship(capacity):
        # Implementation to check if capacity works
        pass
    
    # Your binary search logic here
    return 0

# Submit your solution and check back next week for the detailed answer!

Conclusion

Binary search is a versatile tool that extends far beyond simple array lookups. When approaching a problem, ask yourself: "Is the search space sorted or monotonic?" If the answer is yes, binary search is likely your optimal path. Remember to handle your boundaries carefully—deciding between low < high and low <= high is the most common place where off-by-one errors occur. In interviews, always mention the potential for integer overflow when calculating mid in languages like Java or C++, as it demonstrates deep technical maturity.

https://en.wikipedia.org/wiki/Binary_search_algorithm https://leetcode.com/explore/learn/card/binary-search/ https://visualgo.net/en/bst https://github.com/python/cpython/blob/main/Lib/bisect.py