Binary Search Questions at Meta: What to Expect

Binary search isn't just about finding an element in a sorted array. At Meta, it's a critical pattern for solving optimization problems and searching in massive, distributed datasets where linear scans are impossible. With 117 binary search questions in their question bank (over 8% of their total problems), mastery is non-negotiable for performance in coding interviews. The pattern tests a candidate's ability to reduce a complex problem's search space logarithmically, a fundamental skill for designing efficient systems at scale.

What to Expect — Types of Problems

Meta's binary search problems typically extend beyond textbook implementations. Expect these three categories:

1. Classic & Modified Search: Direct application on sorted arrays, but often with a twist—like searching in a rotated sorted array, finding the first/last occurrence of a target, or searching in a 2D matrix.
2. Search on Answer (Optimization Problems): This is the most common and crucial type. You use binary search to find the optimal value (the "answer") within a feasible range. The core task is writing a helper function (often called canDo or isValid) that checks if a given candidate answer is achievable. Problems include: "Koko Eating Bananas," "Capacity To Ship Packages Within D Days," and "Find the Smallest Divisor Given a Threshold."
3. Search in Structured Data: Applying the divide-and-conquer logic to data structures like infinite streams, sorted but unknown-length lists, or peak-finding problems.

How to Prepare — Study Tips with One Code Example

Focus on the underlying principle: repeatedly dividing a sorted search space. Your mental checklist should be:

• Is the data sorted, or can I sort it?
• Can I define a clear condition that splits the search space into "valid" and "invalid" halves?
• What are my loop invariants? (Use left <= right for inclusive ranges, left < right for exclusive).
• How do I update bounds to avoid infinite loops? (mid + 1 and mid - 1 are typical).

The most important skill is transforming an optimization problem into a binary search. Here is the key pattern for a "Search on Answer" problem, using "Find the Smallest Divisor Given a Threshold" as an example. The goal is to find the smallest integer divisor such that the sum of the division results is less than or equal to a threshold.

def smallestDivisor(nums, threshold):
    def condition(divisor):
        # Helper: checks if this divisor is valid (sum <= threshold)
        total = sum((num + divisor - 1) // divisor for num in nums)  # Ceiling division
        return total <= threshold

    left, right = 1, max(nums)
    while left < right:
        mid = (left + right) // 2
        if condition(mid):
            # If mid works, try a smaller divisor (search left half)
            right = mid
        else:
            # If mid fails, we need a larger divisor (search right half)
            left = mid + 1
    return left

Recommended Practice Order

Build competence sequentially:

1. Fundamentals: Implement standard binary search. Practice variants: find first/last position, search in rotated array.
2. Core Pattern: Solve 2-3 "search on answer" problems (like Koko Eating Bananas). Focus on writing the helper function.
3. Meta-Specific: Practice problems frequently tagged for Meta from their question bank. These often involve the optimization pattern applied to real-world scenarios.
4. Integration: Try problems where binary search is one component of a more complex solution.

Practice Binary Search at Meta