Ojaswi Athghara | Binary Search Algorithm Tutorial: Master Answer Space Search for Interviews

The Question That Changed How I See Binary Search

An interviewer once asked: "You have n workers and k tasks. Each worker can complete tasks at different speeds. What's the minimum time needed to complete all tasks if you can assign tasks optimally?"

I stared at the problem, confused. Where's the sorted array? How is this binary search?

Then the interviewer smiled and said: "Think about searching on the answer space." That single hint unlocked a completely new way of thinking about binary search.

Binary search isn't just for finding elements in sorted arrays—it's about eliminating half of the search space when you can determine which half to discard.

In this guide, I'll share the mental shift that transformed binary search from a simple search algorithm into a powerful problem-solving tool. You'll learn to recognize binary search opportunities in problems that don't look like search at all.

The Classic Binary Search (But Done Right)

Before we explore advanced patterns, let's master the foundation. There are subtle variations in binary search that cause off-by-one errors.

The Standard Template

def binary_search(arr, target):
    """
    Standard binary search template.
    Find index of target, or -1 if not found.
    """
    left, right = 0, len(arr) - 1

    while left <= right:  # Note: <=, not <
        mid = left + (right - left) // 2  # Avoid overflow

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1  # Search right half
        else:
            right = mid - 1  # Search left half

    return -1  # Not found

Key points:

left <= right (not left < right)
mid = left + (right - left) // 2 (avoids integer overflow)
Move left to mid + 1 and right to mid - 1

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

Finding First/Last Occurrence

def find_first_occurrence(arr, target):
    """
    Find leftmost occurrence of target.
    Continue searching left even after finding.
    """
    left, right = 0, len(arr) - 1
    result = -1

    while left <= right:
        mid = left + (right - left) // 2

        if arr[mid] == target:
            result = mid
            right = mid - 1  # Continue searching left
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return result

def find_last_occurrence(arr, target):
    """
    Find rightmost occurrence of target.
    Continue searching right even after finding.
    """
    left, right = 0, len(arr) - 1
    result = -1

    while left <= right:
        mid = left + (right - left) // 2

        if arr[mid] == target:
            result = mid
            left = mid + 1  # Continue searching right
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return result

Test: [1, 2, 2, 2, 3, 4], target = 2

First occurrence: index 1
Last occurrence: index 3

Pattern 1: Binary Search on Answer Space

This is the game-changer. Instead of searching for a value in an array, search for the answer to your question.

When to recognize:

Problem asks for "minimum/maximum value that satisfies condition"
You can check if a value works in O(n) or better
Answer space has monotonic property

The template:

def binary_search_answer(feasible, low, high):
    """
    Binary search on answer space.
    Find minimum/maximum value that satisfies condition.
    """
    result = -1

    while low <= high:
        mid = low + (high - low) // 2

        if feasible(mid):
            result = mid
            # Decide which direction to continue
            # For minimum: high = mid - 1
            # For maximum: low = mid + 1
        else:
            # Move to other half
            pass

    return result

Example: Capacity To Ship Packages

LeetCode #1011 - Capacity To Ship Packages Within D Days

def ship_within_days(weights, days):
    """
    Find minimum ship capacity to ship all packages in D days.
    Binary search on capacity (answer space).
    """
    def can_ship(capacity):
        """Check if we can ship all packages with given capacity."""
        days_needed = 1
        current_load = 0

        for weight in weights:
            if current_load + weight > capacity:
                days_needed += 1
                current_load = weight
            else:
                current_load += weight

        return days_needed <= days

    # Search space: [max_weight, sum_of_all_weights]
    left = max(weights)  # Must carry heaviest package
    right = sum(weights)  # Could ship all in one day
    result = right

    while left <= right:
        mid = left + (right - left) // 2

        if can_ship(mid):
            result = mid
            right = mid - 1  # Try smaller capacity
        else:
            left = mid + 1  # Need larger capacity

    return result

The insight:

We're not searching an array—we're searching possible capacity values
Can check if capacity X works in O(n)
If capacity X works, all capacities > X also work (monotonic)

Test: weights = [1,2,3,4,5,6,7,8,9,10], days = 5 → 15

Example: Koko Eating Bananas

LeetCode #875 - Koko Eating Bananas

def min_eating_speed(piles, h):
    """
    Find minimum eating speed to finish all bananas in h hours.
    Binary search on speed (answer space).
    """
    def can_finish(speed):
        """Check if can eat all bananas at this speed."""
        hours = 0
        for pile in piles:
            hours += (pile + speed - 1) // speed  # Ceiling division
        return hours <= h

    # Search space: [1, max_pile]
    left, right = 1, max(piles)
    result = right

    while left <= right:
        mid = left + (right - left) // 2

        if can_finish(mid):
            result = mid
            right = mid - 1  # Try slower speed
        else:
            left = mid + 1  # Need faster speed

    return result

Pattern recognition: "Minimum X such that condition is met" → Binary search on X

Pattern 2: Rotated and Modified Arrays

Search in Rotated Sorted Array

LeetCode #33 - Search in Rotated Sorted Array

def search_rotated(nums, target):
    """
    Search in rotated sorted array.
    One half is always sorted—use that to decide which half to search.
    """
    left, right = 0, len(nums) - 1

    while left <= right:
        mid = left + (right - left) // 2

        if nums[mid] == target:
            return mid

        # Determine which half is sorted
        if nums[left] <= nums[mid]:  # Left half is sorted
            # Check if target in sorted left half
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:  # Right half is sorted
            # Check if target in sorted right half
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1

    return -1

The trick: At least one half is always properly sorted. Use the sorted half to determine if target is there.

Test: nums = [4,5,6,7,0,1,2], target = 0 → 4

Find Minimum in Rotated Sorted Array

LeetCode #153

def find_min_rotated(nums):
    """
    Find minimum in rotated sorted array.
    Minimum is where rotation happened.
    """
    left, right = 0, len(nums) - 1

    while left < right:
        mid = left + (right - left) // 2

        # If mid > right, minimum is in right half
        if nums[mid] > nums[right]:
            left = mid + 1
        else:
            # Minimum is in left half (including mid)
            right = mid

    return nums[left]

Key insight: Compare nums[mid] with nums[right] to determine which side has the minimum.

Pattern 3: 2D Matrix Search

Search in 2D Matrix (Sorted Row and Column)

LeetCode #74 - Search a 2D Matrix

def search_matrix(matrix, target):
    """
    Search in matrix where each row is sorted,
    and first element of each row > last of previous row.
    Treat as 1D sorted array!
    """
    if not matrix or not matrix[0]:
        return False

    rows, cols = len(matrix), len(matrix[0])
    left, right = 0, rows * cols - 1

    while left <= right:
        mid = left + (right - left) // 2
        # Convert 1D index to 2D
        row = mid // cols
        col = mid % cols
        mid_val = matrix[row][col]

        if mid_val == target:
            return True
        elif mid_val < target:
            left = mid + 1
        else:
            right = mid - 1

    return False

Clever trick: Treat 2D matrix as 1D array by converting indices!

Search in Row and Column Sorted Matrix

LeetCode #240 - Search a 2D Matrix II

def search_matrix_ii(matrix, target):
    """
    Search in matrix where rows and columns are sorted.
    Start from top-right corner: eliminates row or column each step.
    """
    if not matrix or not matrix[0]:
        return False

    rows, cols = len(matrix), len(matrix[0])
    row, col = 0, cols - 1  # Start top-right

    while row < rows and col >= 0:
        if matrix[row][col] == target:
            return True
        elif matrix[row][col] < target:
            row += 1  # Eliminate current row
        else:
            col -= 1  # Eliminate current column

    return False

Why top-right? From there, moving down increases values, moving left decreases them. Each comparison eliminates a row or column!

Time: O(m + n), not O(log n), but elegant!

Pattern 4: Peak Finding

Find Peak Element

LeetCode #162 - Find Peak Element

def find_peak_element(nums):
    """
    Find peak element (element > neighbors).
    Binary search: move towards higher neighbor.
    """
    left, right = 0, len(nums) - 1

    while left < right:
        mid = left + (right - left) // 2

        # If going up, peak is to the right
        if nums[mid] < nums[mid + 1]:
            left = mid + 1
        else:
            # If going down, peak is to the left (or at mid)
            right = mid

    return left

Brilliant insight: Always move towards the higher neighbor. You're guaranteed to find a peak!

The Binary Search Decision Framework

Ask yourself these questions:

1. Is there a sorted array?

YES → Standard binary search

2. Is there a rotated sorted array?

YES → Modified binary search (check which half is sorted)

3. Are you looking for min/max that satisfies condition?

YES → Binary search on answer space
Check: Can you verify if value X works in O(n) or better?

4. Is it a 2D matrix?

Sorted as 1D → Treat as 1D array
Rows and columns sorted → Start top-right or bottom-left

5. Looking for peak/valley?

YES → Move towards increasing side

Common Binary Search Mistakes

Mistake 1: Wrong Loop Condition

# WRONG: Might miss single element
while left < right:  # Should be <=
    ...

# RIGHT: Process until left and right meet
while left <= right:
    ...

Mistake 2: Infinite Loop

# WRONG: Infinite loop when left = mid
left, right = 0, n
while left < right:
    mid = (left + right) // 2
    if condition:
        right = mid  # Good
    else:
        left = mid  # BAD: infinite loop!

# RIGHT: Always progress
left = mid + 1

Mistake 3: Integer Overflow

# WRONG: Might overflow in other languages
mid = (left + right) // 2

# RIGHT: Safe from overflow
mid = left + (right - left) // 2

Mistake 4: Off-by-One Errors

# Finding first occurrence
if arr[mid] == target:
    result = mid
    right = mid - 1  # Continue left, NOT mid

# Finding last occurrence
if arr[mid] == target:
    result = mid
    left = mid + 1  # Continue right, NOT mid

Binary Search Template Variations

Template 1: Standard (left <= right)

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

Use for: Finding exact value, first/last occurrence

Template 2: Left Boundary (left < right)

while left < right:
    mid = left + (right - left) // 2
    if condition:
        right = mid  # Don't exclude mid
    else:
        left = mid + 1
return left

Use for: Finding insertion position, minimum satisfying condition

Template 3: Right Boundary (left < right)

while left < right:
    mid = left + (right - left + 1) // 2  # Bias right
    if condition:
        left = mid  # Don't exclude mid
    else:
        right = mid - 1
return left

Use for: Finding maximum satisfying condition

My Practice Strategy

Week 1: Master the Basics

Implement standard binary search 20 times
Practice first/last occurrence
Handle edge cases: empty, single element, duplicates

Week 2: Rotated Arrays and 2D

Rotated sorted array problems
2D matrix search variations
15-20 problems

Week 3: Answer Space

Capacity, speed, allocation problems
Recognize "minimum X such that..." pattern
15-20 problems

Week 4: Mixed Practice

40+ problems mixing all patterns
Practice recognizing when to use binary search
Time yourself: 15-20 minutes per problem

Real Interview Success

I was asked: "Find the smallest divisor given a threshold."

My thought process:

"Smallest X such that sum(ceil(arri/X)) <= threshold"
This is "minimum X satisfying condition" → Binary search on answer space!
Can check if divisor X works in O(n)

Coded in 12 minutes:

def smallest_divisor(nums, threshold):
    def sum_divided(divisor):
        return sum((num + divisor - 1) // divisor for num in nums)

    left, right = 1, max(nums)
    result = right

    while left <= right:
        mid = left + (right - left) // 2
        if sum_divided(mid) <= threshold:
            result = mid
            right = mid - 1
        else:
            left = mid + 1

    return result

The interviewer was impressed by immediate pattern recognition.

Conclusion: Your Binary Search Mastery

Binary search is more than searching arrays—it's about eliminating half of the search space:

Master the templates - Know when to use each variation
Recognize answer space problems - "Minimum X such that..."
Handle rotated arrays - One half is always sorted
Avoid off-by-one errors - Use correct loop conditions

Start with standard binary search until it's automatic. Then move to answer space problems—they're the most impressive in interviews. Finally, master rotated arrays and 2D matrices.

Within 3-4 weeks of focused practice, you'll recognize binary search opportunities instantly, even in problems that don't mention "search" at all.

Remember: when you can eliminate half the possibilities by checking one element, think binary search!

Happy coding, and may your searches always be logarithmic!

If you found this guide helpful, share it with others learning algorithms. Binary search is fundamental—mastering, it opens many doors. If this guide helped you master binary search beyond arrays or solve answer space search problems, I'd love to hear about it! Connect with me on Twitter or LinkedIn.

Support My Work

If this guide helped you master binary search patterns, recognize answer space problems, or ace search interview questions, I'd really appreciate your support! Creating comprehensive, free content like this takes significant time and effort. Your support helps me continue sharing knowledge and creating more helpful resources for students like you.

☕ Buy me a coffee - Every contribution, big or small, means the world to me and keeps me motivated to create more content!

Cover image by Daniel Lerman on Unsplash

Related Blogs