Binary Search Pattern

What is Binary Search?

Binary Search is a divide-and-conquer algorithm that repeatedly halves the search space. It reduces O(n) linear search to O(log n) by eliminating half the possibilities at each step.

Quick Recognition: If you see “sorted array” or need to minimize/maximize something with a feasibility check, Binary Search is likely the answer!

Pattern Recognition Checklist

Use Binary Search When

Array is sorted (or has monotonic property)
Need O(log n) instead of O(n)
Minimize/maximize with feasibility check
Finding transition point where condition changes
Search space can be halved each step

Don't Use When

Array is unsorted with no order
Need to find all occurrences
Linear scan is already O(n) and sufficient
No clear way to eliminate half

When to Use

Sorted Arrays

Finding elements, insertion points, or bounds

Monotonic Functions

Finding transition points where condition changes

Optimization Problems

Minimizing/maximizing values with feasibility check

Hidden Sorted Space

Rotated arrays, peak finding, matrix search

Pattern Variations

1. Standard Binary Search

Find exact target in sorted array.

def binary_search(arr, target):
    """Find target in sorted array, return index or -1"""
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2  # Avoid overflow
        
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return -1

2. Lower Bound (First Occurrence)

Find first element greater than or equal to target.

def lower_bound(arr, target):
    """Find first index where arr[i] >= target"""
    left, right = 0, len(arr)
    
    while left < right:
        mid = left + (right - left) // 2
        
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid  # Don't exclude mid, it could be answer
    
    return left

3. Upper Bound (Last Occurrence)

Find first element greater than target.

def upper_bound(arr, target):
    """Find first index where arr[i] > target"""
    left, right = 0, len(arr)
    
    while left < right:
        mid = left + (right - left) // 2
        
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
    
    return left

4. Binary Search on Answer

When searching for optimal value, not index.

def min_capacity_to_ship(weights, days):
    """Minimum ship capacity to ship all packages in given 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
    
    # Search space: [max single weight, sum of all weights]
    left = max(weights)
    right = sum(weights)
    
    while left < right:
        mid = left + (right - left) // 2
        
        if can_ship(mid):
            right = mid  # Try smaller capacity
        else:
            left = mid + 1  # Need more capacity
    
    return left

Classic Problems

1. Search in Rotated Sorted Array

Problem: Search for target in rotated sorted array.Approach: Find which half is sorted, determine if target is in that half.Time: O(log n) | Space: O(1)

2. Find Peak Element

Problem: Find any peak element (greater than neighbors).Approach: Compare mid with mid+1, move towards the larger side.Time: O(log n) | Space: O(1)

3. Search 2D Matrix

Problem: Search in row-wise and column-wise sorted matrix.Approach: Treat as 1D array or start from top-right corner.Time: O(log(m*n)) or O(m+n) | Space: O(1)

4. Koko Eating Bananas

Problem: Minimum eating speed to finish all bananas in h hours.Approach: Binary search on answer with feasibility check.Time: O(n log m) | Space: O(1)

5. Median of Two Sorted Arrays

Problem: Find median of two sorted arrays in O(log(m+n)).Approach: Binary search on partition point of smaller array.Time: O(log(min(m,n))) | Space: O(1)

Search in Rotated Sorted Array

def search_rotated(nums, target):
    """Search for target in rotated sorted array"""
    left, right = 0, len(nums) - 1
    
    while left <= right:
        mid = (left + right) // 2
        
        if nums[mid] == target:
            return mid
        
        # Left half is sorted
        if nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # Right half is sorted
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    
    return -1

Template Code

# Template 1: Standard (find exact match)
def binary_search_standard(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

# Template 2: Lower bound (first >= target)
def binary_search_lower(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

# Template 3: Binary search on answer
def binary_search_answer(low, high, is_valid):
    while low < high:
        mid = low + (high - low) // 2
        if is_valid(mid):
            high = mid
        else:
            low = mid + 1
    return low

Common Mistakes

Avoid These Pitfalls:

Integer Overflow: Use mid = left + (right - left) / 2 instead of (left + right) / 2
Infinite Loop: Ensure left or right changes every iteration
Off-by-one: Know when to use left <= right vs left < right
Wrong boundary: Include or exclude mid based on problem type

Debugging Checklist

When your Binary Search solution fails:

Check Initial Bounds

Is left = 0 and right = len - 1 or right = len?

Check Loop Condition

Use left <= right for exact match, left < right for bounds.

Check Mid Calculation

Use left + (right - left) / 2 to avoid overflow.

Check Movement

Is mid included or excluded? (right = mid vs right = mid - 1)

Check Return Value

What should be returned when element is not found?

The Three Templates

Understanding which template to use is crucial:

Template	Loop Condition	Use Case	After Loop
Standard	`left <= right`	Find exact match	Return -1 if not found
Lower Bound	`left < right`	First >= target	`left` is answer
Upper Bound	`left < right`	First > target	`left` is answer

Complexity Quick Reference

Problem Type	Time	Space	Key Insight
Standard search	O(log n)	O(1)	Exact match
Lower/Upper bound	O(log n)	O(1)	First occurrence
Search on answer	O(n log range)	O(1)	Feasibility check
Rotated array	O(log n)	O(1)	Find sorted half
Peak finding	O(log n)	O(1)	Compare with neighbor

Interview Problems by Company

Easy
Medium
Hard

Problem	Company	Key Concept
Binary Search	All	Basic template
Search Insert Position	Amazon, Google	Lower bound
First Bad Version	Meta, Microsoft	Boolean search
Sqrt(x)	Amazon	Search on answer
Valid Perfect Square	Google	Search on answer

Problem	Company	Key Concept
Search Rotated Array	All FAANG	Modified search
Find Peak Element	Meta, Microsoft	Monotonic property
Find First and Last Position	Amazon	Double binary search
Search 2D Matrix	Google	Flattened search
Koko Eating Bananas	Google	Search on answer

Problem	Company	Key Concept
Median of Two Sorted Arrays	Google, Amazon	Partition search
Split Array Largest Sum	Google	Search on answer
Find in Mountain Array	Google	Peak + two searches
Smallest Good Base	Google	Math + binary search

Interview Tips

How to Explain Your Approach

Script for interviews:

“Since the array is sorted, I can use Binary Search for O(log n) time.”
“I’ll maintain two pointers, left and right, representing the search space.”
“At each step, I calculate mid and compare with target.”
“Based on comparison, I eliminate half the search space.”
“I repeat until I find the target or the space is exhausted.”

When Interviewer Says...

Interviewer Says	You Should Think
”Array is sorted”	Binary Search!
”Can you do better than O(n)?”	Binary Search might work
”Find minimum/maximum that satisfies…”	Binary Search on answer
”Array is rotated”	Modified Binary Search
”Find first/last occurrence”	Lower/Upper bound

Common Follow-ups

Be ready for these follow-ups:

“What if there are duplicates?” → Use lower/upper bound
“What if array is rotated?” → Find sorted half first
“Can you do it without extra space?” → Binary Search is already O(1) space
“What about very large arrays?” → Binary Search scales well

Practice Problems

Problem	Difficulty	Link
Binary Search	Easy	LeetCode 704
Search Insert Position	Easy	LeetCode 35
Search in Rotated Sorted Array	Medium	LeetCode 33
Find Peak Element	Medium	LeetCode 162
Median of Two Sorted Arrays	Hard	LeetCode 4

Practice Roadmap

Day 1: Standard Search

Solve: Binary Search, Search Insert Position
Focus: Master the basic template perfectly

Day 2: Bounds

Solve: Find First and Last Position, First Bad Version
Focus: Lower bound vs upper bound

Day 3: Modified Arrays

Solve: Search in Rotated Array, Find Peak Element
Focus: Finding the sorted half

Day 4: Search on Answer

Solve: Koko Eating Bananas, Capacity To Ship
Focus: Binary search on the result space

Interview Tip: When you see “sorted array” or “minimize/maximize” with a feasibility check, think Binary Search immediately.

Overview

Array & String

Search & Sort

Data Structures

Graph & Tree

Advanced Techniques

What is Binary Search?

Pattern Recognition Checklist

Use Binary Search When

Don't Use When

When to Use

Sorted Arrays

Monotonic Functions

Optimization Problems

Hidden Sorted Space

Pattern Variations

1. Standard Binary Search

2. Lower Bound (First Occurrence)

3. Upper Bound (Last Occurrence)

4. Binary Search on Answer

Classic Problems

Search in Rotated Sorted Array

Template Code

Common Mistakes

Debugging Checklist

The Three Templates

Complexity Quick Reference

Interview Problems by Company

Interview Tips

Practice Problems

Practice Roadmap

Overview

Array & String

Search & Sort

Data Structures

Graph & Tree

Advanced Techniques

​What is Binary Search?

​Pattern Recognition Checklist

Use Binary Search When

Don't Use When

​When to Use

Sorted Arrays

Monotonic Functions

Optimization Problems

Hidden Sorted Space

​Pattern Variations

​1. Standard Binary Search

​2. Lower Bound (First Occurrence)

​3. Upper Bound (Last Occurrence)

​4. Binary Search on Answer

​Classic Problems

​Search in Rotated Sorted Array

​Template Code

​Common Mistakes

​Debugging Checklist

​The Three Templates

​Complexity Quick Reference

​Interview Problems by Company

​Interview Tips

​Practice Problems

​Practice Roadmap

What is Binary Search?

Pattern Recognition Checklist

When to Use

Pattern Variations

1. Standard Binary Search

2. Lower Bound (First Occurrence)

3. Upper Bound (Last Occurrence)

4. Binary Search on Answer

Classic Problems

Search in Rotated Sorted Array

Template Code

Common Mistakes

Debugging Checklist

The Three Templates

Complexity Quick Reference

Interview Problems by Company

Interview Tips

Practice Problems

Practice Roadmap