How to Recognize Binary Search Problems in 30 Seconds (Interview Pattern Recognition)

You're in an interview. The problem doesn't mention "binary search." How do you know if it's a binary search problem?

Pattern recognition is a critical interview skill. This guide teaches you the 30-second checklist, keyword recognition, common disguises, and how to verify your intuition.

TL;DR

The 30-second checklist:

1. ✅ Sorted data or monotonic property?
2. ✅ "Minimize maximum" or "maximize minimum"?
3. ✅ Large search space with clear bounds?
4. ✅ Can verify if a candidate answer works?

If 3+ are yes → Binary search

The 30-Second Checklist

Signal 1: Sorted Data

Look for:

• "Sorted array"
• "Non-decreasing order"
• "Ascending/descending"
• "Sorted matrix"

Examples:

• "Given a sorted array..." → Binary search ✓
• "Search in rotated sorted array..." → Binary search variant ✓
• "Find element in sorted matrix..." → Binary search ✓

Signal 2: "Minimize/Maximize" Language

Look for:

• "Minimize the maximum..."
• "Maximize the minimum..."
• "Find the smallest X such that..."
• "Find the largest Y while..."

Examples:

• "Minimize eating speed..." → Binary search on answer ✓
• "Maximize minimum distance..." → Binary search on answer ✓
• "Find smallest divisor..." → Binary search on answer ✓

Signal 3: Large Search Space

Look for:

• Answer range is large (10⁴ to 10⁹)
• "Find in range [1, 10⁹]"
• Time limit suggests O(log n) needed

Examples:

• "Speed can be from 1 to 10⁹" → Binary search on answer ✓
• "Array of 10⁶ elements" → Need O(log n) → Binary search ✓

Signal 4: Monotonic Function

Look for:

• "If X works, X+1 also works"
• "If X doesn't work, X-1 also doesn't work"
• Feasibility has a clear direction

Examples:

• "If speed k works, faster speeds also work" → Monotonic ✓
• "If distance d works, smaller distances also work" → Monotonic ✓

Common Disguises

Disguise 1: No Explicit Array

Problem: "Find square root of x"

Hidden binary search:

• Search space: [0, x]
• Monotonic: if mid² < x, answer is in [mid, x]
• Binary search on answer ✓

def sqrt(x):
    left, right = 0, x
    while left <= right:
        mid = left + (right - left) // 2
        if mid * mid == x:
            return mid
        elif mid * mid < x:
            left = mid + 1
        else:
            right = mid - 1
    return right

Disguise 2: Optimization Problem

Problem: "Koko eating bananas"

Hidden binary search:

• Not explicitly "search"
• But: "minimize speed" → binary search on answer
• Feasibility: can finish with speed k?

Disguise 3: "Find First/Last"

Problem: "Find first bad version"

Hidden binary search:

• "First" suggests lower bound
• Sorted property: [G, G, G, B, B, B]
• Binary search for boundary ✓

Disguise 4: Matrix Problems

Problem: "Search 2D matrix"

Hidden binary search:

• Matrix is sorted → treat as 1D array
• Binary search with index mapping ✓

Keyword Recognition

Binary Search Keywords

Explicit:

• "Binary search"
• "Search in sorted..."
• "Find in O(log n)"

Implicit:

• "Minimize the maximum"
• "Maximize the minimum"
• "Find first occurrence"
• "Find last occurrence"
• "Search insert position"

Anti-Keywords (NOT Binary Search)

These suggest other patterns:

• "Maximum subarray" → Kadane's algorithm
• "Longest substring" → Sliding window
• "All pairs" → Two pointers or hash map
• "Dynamic programming" → DP
• "Shortest path" → BFS/Dijkstra

Decision Framework

Step 1: Check for sorted data
├─ Sorted array? → Classic binary search
├─ Rotated sorted? → Rotated binary search
├─ Sorted matrix? → 2D binary search
└─ No explicit array? → Continue

Step 2: Check for optimization
├─ "Minimize maximum"? → Binary search on answer
├─ "Maximize minimum"? → Binary search on answer
└─ Neither? → Continue

Step 3: Check for monotonicity
├─ Can verify if X works? → Continue
├─ If X works, does X±1 work? → Binary search on answer
└─ No monotonicity? → Not binary search

Step 4: Check constraints
├─ Large search space? → Suggests O(log n)
├─ Need O(log n)? → Binary search
└─ O(n) acceptable? → Might not need binary search

Practice Examples

Example 1: Identify the Pattern

Problem: "Given a sorted array of integers, find the first and last position of a given target value."

Analysis:

• ✅ Sorted array
• ✅ "First and last" → lower/upper bound
• ✅ Can use binary search
• Pattern: Lower bound + upper bound

Example 2: Hidden Binary Search

Problem: "A conveyor belt has packages with weights. Ship all packages within D days. Find minimum ship capacity."

Analysis:

• ❌ No explicit sorted array
• ✅ "Minimize capacity" → optimization
• ✅ If capacity C works, C+1 works → monotonic
• ✅ Can verify if capacity works
• Pattern: Binary search on answer

Example 3: Not Binary Search

Problem: "Find the longest substring without repeating characters."

Analysis:

• ❌ Not sorted
• ❌ Not optimization with monotonic feasibility
• ❌ "Longest substring" → sliding window keyword
• Pattern: Sliding window (NOT binary search)

Example 4: Disguised Binary Search

Problem: "Find the peak element in an array where arr[i] != arr[i+1]."

Analysis:

• ❌ Not sorted
• ✅ But has monotonic property: if arr[mid] < arr[mid+1], peak is to the right
• ✅ Can use binary search logic
• Pattern: Modified binary search

Common Mistakes

Mistake 1: Assuming All "Search" Problems Use Binary Search

❌ Wrong:

"Search for two numbers that sum to target"
→ Must be binary search!

✅ Correct:

Check if sorted:
- Sorted → Two pointers (binary search variant)
- Unsorted → Hash map (NOT binary search)

Mistake 2: Missing Hidden Binary Search

❌ Wrong:

"Minimize eating speed"
→ Sounds like greedy or DP

✅ Correct:

"Minimize" + monotonic feasibility
→ Binary search on answer!

Mistake 3: Forcing Binary Search

❌ Wrong:

"Find maximum subarray sum"
→ Try binary search?

✅ Correct:

No sorted property, no monotonic feasibility
→ Use Kadane's algorithm (NOT binary search)

Quick Reference

Practice Strategy

Step 1: Solve these classic problems

1. Binary Search (#704)
2. Search Insert Position (#35)
3. First Bad Version (#278)
4. Find First and Last Position (#34)
5. Koko Eating Bananas (#875)

Step 2: Practice recognition

• Read problem
• Apply 30-second checklist
• Identify pattern before coding

Step 3: Learn disguises

• Solve problems that don't mention "binary search"
• Recognize optimization patterns
• Identify monotonic properties

FAQ

Q: What if the problem doesn't mention "sorted"?

A: Check for monotonic properties or optimization keywords ("minimize maximum").

Q: How do I know if it's binary search vs sliding window?

A:

• Binary search: Sorted or monotonic, O(log n)
• Sliding window: Contiguous subarray/substring, O(n)

Q: Can I use binary search on unsorted data?

A: Only if there's a monotonic property (e.g., binary search on answer).

Q: What if I'm not sure?

A: Ask: "Can I eliminate half the search space with each decision?" If yes, likely binary search.

Conclusion

Recognizing binary search problems in 30 seconds is a learnable skill.

The checklist:

1. Sorted data?
2. Optimization keywords?
3. Large search space?
4. Monotonic property?

Common disguises:

• No explicit array (binary search on answer)
• Optimization problems (minimize/maximize)
• "Find first/last" (lower/upper bound)
• Matrix problems (2D binary search)

Decision framework:

1. Check for sorted data
2. Check for optimization
3. Check for monotonicity
4. Verify with constraints

Practice:

• Solve classic problems
• Practice recognition
• Learn disguises

Master pattern recognition and you'll identify binary search opportunities instantly. For more details, see Binary Search on Answer, Why Binary Search Requires Sorted Data, and the Complete Binary Search Guide.

Next time you see a problem, run through the 30-second checklist. You'll know if it's binary search before you write a single line of code.