Binary Search Pattern - Dev Weekends

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. Imagine looking up a word in a physical dictionary. You would never start at page 1 and read every page. Instead, you open to the middle, decide if your word comes before or after that page, and repeat on the correct half. Each flip eliminates roughly half the remaining pages. That is binary search: a disciplined halving of possibilities. The key insight is that binary search does not require a “sorted array” specifically — it requires a monotonic predicate. If you can define a condition that is false for all values below some threshold and true for all values above it (or vice versa), you can binary-search for that threshold. This generalization is what enables “binary search on the answer” for optimization problems, which is arguably the most common interview pattern. Complexity: O(log n) time, O(1) space. For a billion-element array, that is about 30 comparisons instead of a billion — one of the most dramatic efficiency wins in all of computer science.

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 Cheatsheet

Map keywords in the problem statement to the binary search variant. If you see one of these, reach for the matching template.

Problem Keyword	Technique	Template to Reach For
”sorted array, find target”	Standard binary search	`left <= right`, return -1 if not found
”find first occurrence”, “leftmost”, “lower bound”, “insertion point”	Lower-bound search	`left < right`, `right = mid` when condition holds
”find last occurrence”, “rightmost”, “upper bound”	Upper-bound search	`left < right`, condition uses strict greater
”find peak element”, “find a local max”	Compare mid with mid+1, walk uphill	`left < right`, halve toward larger neighbor
”rotated sorted array”, “minimum in rotated”, “search in rotated”	Find which half is sorted, then decide	Standard template with extra branching
”minimize the maximum X”, “maximize the minimum X”	Binary search on the answer	Define monotonic predicate, search answer space
”minimum capacity”, “minimum time”, “smallest divisor”	Binary search on the answer (minimization)	`left < right`, `right = mid` if feasible
”largest possible X”, “maximum K such that…”	Binary search on the answer (maximization)	`left < right`, ceiling mid + `left = mid` if feasible
”search in 2D matrix” (rows AND cols sorted)	Staircase search from top-right	O(m+n), not binary search
”search in 2D matrix” (each row sorted, rows chained)	Treat as 1D sorted, binary search	Flatten with row = mid / n, col = mid % n
”median of two sorted arrays”	Binary search on partition position	Search smaller array’s partition point

Rule of thumb: anything that says “minimum/maximum X such that Y holds” is binary search on the answer. Anything with explicit sorted input is standard or bounds. If the data is unsorted but has a monotonic property along an axis (peak finding, mountain arrays), it is still binary search.

Universal Templates

These three templates cover roughly 95% of binary search interview problems. The single most important insight: pick a template and stick to it for that problem — do not mix conventions.

Template 1: Exact Match (`left <= right`)

Use when the answer is a specific element in a sorted array, and “not found” returns -1.

def standard(arr, target):
    left, right = 0, len(arr) - 1            # closed interval [left, right]
    while left <= right:                      # search until interval is empty
        mid = left + (right - left) // 2      # overflow-safe midpoint
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1                    # exclude mid -- it is too small
        else:
            right = mid - 1                   # exclude mid -- it is too big
    return -1

Template 2: Lower Bound — the canonical interview template (`left < right`)

Use this for first occurrence, insertion point, first element satisfying a predicate, and most “binary search on the answer” problems. The convergence is left == right == answer.

def lower_bound(arr, target):
    left, right = 0, len(arr)                 # right = len(arr), one past the end!
    while left < right:                        # converge until left == right
        mid = left + (right - left) // 2       # floor mid
        if arr[mid] < target:
            left = mid + 1                     # mid is too small -- exclude
        else:
            right = mid                        # mid might be the answer -- KEEP
    return left                                 # left == right == answer

Why left < right and not left <= right here? Because right = mid (not mid - 1) keeps mid in the range. If you used left <= right with right = mid, then when left == right == mid, the next iteration sets right = mid again — no progress, infinite loop. Why left = mid + 1 and not left = mid? Because mid was just shown to be too small (arr[mid] < target), so excluding it is safe. If you wrote left = mid, then at left + 1 == right, mid equals left, and you would loop forever. The pattern is rigid: left < right, floor mid, right = mid when condition holds, left = mid + 1 when it does not. Memorize it.

Template 3: Upper Bound (`left < right` with strict comparison)

To find first element strictly greater than target:

def upper_bound(arr, target):
    left, right = 0, len(arr)
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] <= target:                 # <= instead of <
            left = mid + 1
        else:
            right = mid
    return left

Trick: last_occurrence(target) == upper_bound(target) - 1 (and verify the value matches).

How to choose mid for upper-bound (when `left = mid` is needed)

Some upper-bound flavors use left = mid instead of left = mid + 1 (when you want mid to potentially be the answer in the increasing-from-left direction). In that case, you MUST use ceiling division for mid:

mid = left + (right - left + 1) // 2          # ceiling -- biases toward right

Otherwise, when left + 1 == right, mid equals left, and left = mid makes no progress — infinite loop. The ceiling shifts mid toward the right so the update always moves forward. This pattern is rare but appears in problems like “find the largest K such that condition” written with left = mid.

Caveats and Traps — read these BEFORE you start coding.

Off-by-one between left <= right vs left < right. Pick one and stick with it for that problem. Do NOT switch mid-coding. The most common bug is using left <= right with right = mid (instead of right = mid - 1) — this can infinite-loop when left == right == mid. Match the loop condition to the update rule: closed interval (<=) goes with mid +/- 1; converging interval (<) goes with right = mid.
(left + right) / 2 overflow in Java/C++. When left and right are both close to INT_MAX, the sum overflows to a negative number, producing a negative mid and an out-of-bounds crash. Always write left + (right - left) / 2. This was a real bug in Java’s Arrays.binarySearch for nearly a decade until Joshua Bloch flagged it in 2006. In Python this is technically unnecessary (arbitrary-precision ints), but write it anyway — it shows awareness and hardens you for non-Python languages.
Binary search on the answer requires a monotonic predicate — define it first. Before writing any code, articulate: “If X works, does X+1 also work?” If yes, you can binary search for the smallest X. If the predicate is non-monotonic (multiple transitions between false and true), binary search converges to one transition and silently misses the others. When in doubt, plot the predicate over a few sample values to confirm.
Forgetting to update left or right. Every iteration must shrink the search space. If neither pointer changes, you have an infinite loop. Check that every branch of your if/else moves at least one pointer.
Wrong initial bounds. For lower bound, right = len(arr) (NOT len(arr) - 1) — the answer might be “insert past the end.” For “binary search on the answer” problems, set left = minimum possible answer and right = maximum possible answer. Setting left = 0 when the minimum is 1 (e.g., Koko Eating Bananas) causes the feasibility check to receive zero and divide by zero.
Confusing rotated-array index with sorted-array index. When searching in a rotated array, do NOT assume arr[left] is the smallest — after rotation, the smallest could be anywhere. Always check which half is sorted using arr[left] <= arr[mid] (the = matters for two-element subarrays where left == mid).
Duplicates in rotated array degrade to O(n). When arr[left] == arr[mid] == arr[right], you cannot determine which half is sorted. The only safe move is left += 1. Worst case becomes O(n) for inputs like [1,1,1,1,1,1,3,1,1].

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. The loop invariant is: “the target, if it exists, is within [left, right].” When left > right, the interval is empty and the target does not exist. Why left + (right - left) // 2 instead of (left + right) // 2? In Java/C++, left + right can overflow a 32-bit integer when both are large. The subtraction form avoids this. In Python it does not matter (arbitrary precision), but using the safe form is good habit. Time: O(log n). Space: O(1).

def binary_search(arr, target):
    """Find target in sorted array, return index or -1"""
    left, right = 0, len(arr) - 1
    
    while left <= right:                      # Loop while search interval is non-empty
        mid = left + (right - left) // 2      # Safe midpoint (avoids overflow)
        
        if arr[mid] == target:
            return mid                        # Found -- return index
        elif arr[mid] < target:
            left = mid + 1                    # Target is in the right half
        else:
            right = mid - 1                   # Target is in the left half
    
    return -1  # Exhausted the search space -- target not present

2. Lower Bound (First Occurrence)

Find the first index where arr[i] >= target. Notice two critical differences from standard search: (1) right starts at len(arr) (one past the end, because the answer might be “insert at the end”), and (2) the loop condition is left < right (not <=), because left == right means we have converged on the answer. When arr[mid] >= target, we do right = mid (not mid - 1) because mid itself might be the answer — we cannot discard it. Use this for: finding insertion points, first occurrence of a value, first position meeting a condition.

def lower_bound(arr, target):
    """Find first index where arr[i] >= target"""
    left, right = 0, len(arr)     # Note: right = len(arr), not len(arr)-1
    
    while left < right:            # Converge until left == right
        mid = left + (right - left) // 2
        
        if arr[mid] < target:
            left = mid + 1         # mid is too small -- exclude it
        else:
            right = mid            # mid could be the answer -- keep it
    
    return left  # left == right == first position where arr[i] >= target

3. Upper Bound (Last Occurrence)

Find the first index where arr[i] > target. This is the mirror image of lower bound: instead of >=, we use >. The only code difference is changing < to <= in the comparison — but that single character changes the semantics entirely. How it relates to lower bound: upper_bound(target) is the same as lower_bound(target + 1) for integers. For finding the last occurrence of a value, compute upper_bound(target) - 1 and verify that position holds the target. Walked example: arr = [1, 3, 3, 3, 5, 7], target = 3. We want the first index where arr[i] > 3, which is index 4 (value 5). So upper_bound = 4. The last occurrence of 3 is at index 4 - 1 = 3. Use this for: finding the last occurrence of a value (upper_bound - 1), counting occurrences (upper_bound - lower_bound), finding the range of equal elements.

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

This is arguably the most important binary search pattern for interviews. Instead of searching for an element in an array, you search for the optimal value in a continuous answer space. The pattern always has three parts:

Define the search space — what is the minimum and maximum possible answer?
Write a feasibility function — given a candidate answer, can we satisfy the constraints?
Binary search on the answer space using the feasibility function as the monotonic predicate.

When to recognize it: Any problem that says “minimize the maximum” or “maximize the minimum” is almost certainly binary search on the answer. Time: O(n * log(range)) where n is the cost of the feasibility check and range is the answer space size.

def min_capacity_to_ship(weights, days):
    """Minimum ship capacity to ship all packages in given days"""
    
    def can_ship(capacity):
        """Feasibility check: can we ship everything in 'days' days?"""
        current_weight = 0
        days_needed = 1            # At least one day is required
        
        for weight in weights:
            if current_weight + weight > capacity:
                days_needed += 1   # Start a new day
                current_weight = 0
            current_weight += weight
        
        return days_needed <= days
    
    # SEARCH SPACE: smallest possible capacity is the heaviest package
    # (can't split a package), largest is shipping everything in one day.
    left = max(weights)
    right = sum(weights)
    
    while left < right:
        mid = left + (right - left) // 2
        
        if can_ship(mid):
            right = mid        # Feasible -- try an even smaller capacity
        else:
            left = mid + 1     # Not feasible -- need more capacity
    
    return left  # Smallest feasible capacity

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

A sorted array that has been rotated at some pivot (e.g., [4,5,6,7,0,1,2]) loses its global order but retains a useful property: at any midpoint, at least one half is still sorted. The trick is to determine which half is sorted, then check if the target falls within that sorted half. If it does, search there; otherwise, search the other half. How to tell which half is sorted: If nums[left] <= nums[mid], the left half [left..mid] is sorted. Otherwise, the right half [mid..right] is sorted. The <= (not <) handles the case where left == mid (subarray of size 1 or 2). Walked example: nums = [4,5,6,7,0,1,2], target = 0. left=0, right=6, mid=3 (value 7). Left half [4,5,6,7] is sorted, but 0 is not in [4,7], so search right. left=4, right=6, mid=5 (value 1). Right half [1,2] is sorted, 0 is not in [1,2], so search left. left=4, right=4, mid=4 (value 0). Found at index 4. Edge case: Duplicates break this approach because nums[left] == nums[mid] no longer tells you which half is sorted. With duplicates, the worst case degrades to O(n). The standard workaround is to skip duplicates: if nums[left] == nums[mid]: left += 1; continue. Time: O(log n) without duplicates. Space: O(1).

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. This matters in Java/C++ where int is 32-bit. An overflow here silently produces a negative index, causing an ArrayIndexOutOfBoundsException.
Infinite Loop: Every iteration must change either left or right. If you write right = mid in a loop that uses left <= right, you risk an infinite loop when left == right == mid. Match your loop condition to your update rule: left <= right with mid +/- 1, or left < right with right = mid.
Off-by-one errors: The three templates have different loop conditions and different right-pointer initializations for a reason. Using left <= right when you should use left < right (or vice versa) is the most common source of off-by-one bugs. When in doubt, trace through a 2-element array on paper.
Wrong boundary after search: After the loop, left and right point to different things depending on the template. For lower bound, left is the answer. For standard search, the element was found inside the loop or does not exist. Always verify what left means when the loop exits.
Confusing the three templates: The standard search (left <= right), lower bound (left < right, right = mid), and upper bound (left < right, left = mid + 1) are distinct. Mixing patterns (e.g., using right = mid - 1 in a lower-bound search) silently skips valid answers.

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

Worked LeetCode Problems

These six problems span the full binary-search surface area: standard search, search in modified arrays, peak finding, and binary search on the answer. Drill these to instinct.

LC 704 — Binary Search (Easy)

Brute force: linear scan. O(n). Optimized: standard binary search. O(log n) time, O(1) space.

def search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

This is the warmup. If you cannot write it cleanly in 60 seconds, the rest of this chapter will not stick.

LC 33 — Search in Rotated Sorted Array (Medium)

Brute force: linear scan. O(n) — ignores the structure entirely. Optimized: at each step, determine which half is sorted, then check if target is inside that sorted half. O(log n).

def search(nums, target):
    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
            if nums[left] <= target < nums[mid]:     # target is in left half
                right = mid - 1
            else:
                left = mid + 1
        else:                                         # right half is sorted
            if nums[mid] < target <= nums[right]:    # target is in right half
                left = mid + 1
            else:
                right = mid - 1
    return -1

Why nums[left] <= nums[mid] and not strict <? When left == mid (subarray of size 1 or 2), the “left half” is a single element and is trivially sorted. Strict < would misclassify it.

LC 153 — Find Minimum in Rotated Sorted Array (Medium)

Brute force: linear scan. O(n). Optimized: binary search using the property that the minimum is the unique element smaller than its predecessor. O(log n).

def findMin(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] > nums[right]:
            left = mid + 1                # min is to the right of mid
        else:
            right = mid                    # min is mid or to the left
    return nums[left]

Why compare with nums[right] and not nums[left]? Because nums[left] could be larger than nums[right] even after we have narrowed in. Comparing with nums[right] gives a clean signal: if mid > right, the rotation point (and min) lies strictly to the right. Otherwise, the min is at or before mid.

LC 162 — Find Peak Element (Medium)

Brute force: linear scan, return any index where nums[i] > nums[i+1]. O(n). Optimized: binary search. The “uphill” direction always contains a peak (because boundaries are -infinity). O(log n).

def findPeakElement(nums):
    left, right = 0, len(nums) - 1
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < nums[mid + 1]:
            left = mid + 1                # uphill to the right -- peak is there
        else:
            right = mid                    # uphill or flat to the left -- peak is there
    return left

Key insight: this is binary search on an unsorted array. The structure that enables it is monotonicity in the “uphill direction” plus the boundary guarantee. The problem promises nums[-1] = nums[n] = -infinity, which guarantees a peak exists.

LC 410 — Split Array Largest Sum (Hard)

Brute force: try all ways to split the array into k subarrays. Exponential. Optimized: binary search on the answer. The answer space is [max(nums), sum(nums)], and the predicate “can we split into at most k subarrays each with sum at most X?” is monotonic in X.

def splitArray(nums, k):
    def can_split(max_sum):
        groups = 1
        current = 0
        for n in nums:
            if current + n > max_sum:
                groups += 1
                current = n
                if groups > k:
                    return False
            else:
                current += n
        return True

    left, right = max(nums), sum(nums)     # smallest possible to largest possible
    while left < right:
        mid = left + (right - left) // 2
        if can_split(mid):
            right = mid                     # mid works -- try smaller
        else:
            left = mid + 1                  # mid too small -- need bigger
    return left

Why left = max(nums)? Because no matter how we split, every subarray’s sum is at least the largest single element (we cannot break elements apart). Setting left lower makes can_split always return false for those values, wasting iterations. Why right = sum(nums)? Because the largest possible answer is “put everything in one subarray,” which requires capacity equal to the total sum.

LC 875 — Koko Eating Bananas (Medium)

Brute force: try every speed from 1 to max(piles). O(max(piles) * n). Optimized: binary search on the answer. The predicate “can Koko finish at speed K within H hours?” is monotonic in K.

def minEatingSpeed(piles, h):
    def can_finish(k):
        hours = 0
        for p in piles:
            hours += (p + k - 1) // k       # ceiling division -- avoid floats
        return hours <= h

    left, right = 1, max(piles)
    while left < right:
        mid = left + (right - left) // 2
        if can_finish(mid):
            right = mid                     # this speed works -- try slower
        else:
            left = mid + 1                  # too slow -- speed up
    return left

Why right = max(piles) and not sum(piles)? Because at speed max(piles), Koko finishes the largest pile in 1 hour, and every smaller pile in 1 hour each, totaling at most n hours. Since the problem guarantees n <= h, this is always feasible. Using a tighter upper bound saves a few iterations. Why ceiling division (p + k - 1) // k and not math.ceil(p / k)? Floating-point division introduces precision errors that break the comparison at edge values. Integer ceiling division is exact and faster.

Curated LeetCode List

A focused grind list grouped by difficulty. Solve all of these and you have covered the full binary-search surface area at FAANG.

#	Problem	Difficulty	Pattern	Why It Matters
704	Binary Search	Easy	Standard template	The warmup — master this in 60 seconds.
35	Search Insert Position	Easy	Lower bound	Canonical lower-bound application.
278	First Bad Version	Easy	Lower bound on boolean	Tests transition-point recognition.
69	Sqrt(x)	Easy	Binary search on answer	Gateway to the “search on answer” pattern.
367	Valid Perfect Square	Easy	Binary search on answer	Same skeleton as Sqrt.
374	Guess Number Higher or Lower	Easy	Standard with API call	Tests minimizing API calls.
33	Search in Rotated Sorted Array	Medium	Find sorted half	The classic rotated-array problem.
81	Search in Rotated Sorted Array II	Medium	Rotated with duplicates	O(n) worst case — know when.
153	Find Minimum in Rotated Sorted Array	Medium	Compare with right boundary	Cleaner than LC 33 — great warmup.
154	Find Minimum in Rotated II	Hard	Duplicates handling	Same as 153 but with `right -= 1` on ties.
162	Find Peak Element	Medium	Walk uphill	Binary search WITHOUT a sorted array.
34	Find First and Last Position	Medium	Lower + upper bound	Tests both bound templates back to back.
74	Search a 2D Matrix	Medium	Flatten to 1D	Mind the row/col index math.
240	Search a 2D Matrix II	Medium	Staircase from top-right	NOT binary search — O(m+n).
875	Koko Eating Bananas	Medium	Binary search on answer	The canonical “search on answer” problem.
1011	Capacity to Ship Packages	Medium	Binary search on answer	Same skeleton as Koko.
1482	Minimum Days to Make Bouquets	Medium	Binary search on answer	Tests greedy feasibility check.
1539	Kth Missing Positive Number	Easy	Lower bound on transformed	Tests creative predicate design.
4	Median of Two Sorted Arrays	Hard	Binary search on partition	The hardest binary search problem.
410	Split Array Largest Sum	Hard	Binary search on answer	”Minimize the maximum” — canonical pattern.
668	Kth Smallest in Multiplication Table	Hard	Binary search + count	Search-on-answer with non-trivial count.
719	Find Kth Smallest Pair Distance	Hard	Binary search + sliding window	Search on distance values.
4	Median of Two Sorted Arrays	Hard	Partition search	Truly hard; staff-level question.

Suggested order: 704 to 35 to 278 to 69 to 33 to 153 to 162 to 34 to 74 to 875 to 1011 to 1482 to 410 to 4.

Interview Q&A — Senior-Level Walkthroughs

Q: Find the first and last position of an element in a sorted array (LC 34).

What interviewers are really testing: Whether you understand lower bound and upper bound as distinct operations and can implement both correctly. Off-by-one errors are immediate and obvious here — “almost right” fails the test cases.Strong Answer Framework:

Recognize that “first position” is lower bound and “last position” is upper bound minus 1.
Run two separate binary searches. Both use Template 2 (left < right).
After each search, validate that the returned index actually contains the target (otherwise the target is not present).
State complexity: O(log n) per search, O(log n) total. O(1) space.

Real LeetCode Example — LC 34 (full code):

def searchRange(nums, target):
    if not nums:
        return [-1, -1]

    # First position: lower bound of target
    left, right = 0, len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid                       # mid might be first occurrence
    first = left
    if first == len(nums) or nums[first] != target:
        return [-1, -1]

    # Last position: upper bound of target minus 1
    left, right = 0, len(nums)
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid] <= target:
            left = mid + 1                    # everything at mid is consumed
        else:
            right = mid
    last = left - 1                            # upper bound is one past, so subtract 1

    return [first, last]

Walkthrough for nums = [5,7,7,8,8,10], target = 8:

First search: looking for first index where nums[i] >= 8. Converges to index 3.
Second search: looking for first index where nums[i] > 8. Converges to index 5. Last = 5 - 1 = 4.
Result: [3, 4].

Senior follow-up 1: “Can you express both first and last using a single lower_bound function?” Answer: yes. last_occurrence(target) == lower_bound(target + 1) - 1. This works because the first index strictly greater than target is one past the last occurrence. Java’s Collections.binarySearch returns this directly via its return-value contract.

Senior follow-up 2: “How do you count the number of occurrences in O(log n)?” Answer: upper_bound(target) - lower_bound(target). The two searches run in O(log n), and subtracting two indices is O(1). This is much better than finding any occurrence and then linearly scanning, which is O(n) when all elements are equal.

Senior follow-up 3: “If you also got the constraint ‘no extra space at all,’ how would your code change?” Answer: it would not — both searches already use O(1) space. The recursion stack is not an issue because we wrote them iteratively. If asked to write it recursively, mention that recursion adds O(log n) stack space, which is technically not O(1).

Common Wrong Answers:

“Find any occurrence with standard binary search, then scan left and right linearly.” This is O(n) worst case (imagine an array of all equal values).
Mixing template conventions — using right = len(nums) - 1 with right = mid, which can infinite-loop or skip the answer.
Not validating that nums[first] == target after the first search. If target is absent, first points to where it would be inserted, not to an actual occurrence.

Further Reading:

LC 34 (Find First and Last Position) — the source problem.
LC 35 (Search Insert Position) — pure lower bound.
LC 278 (First Bad Version) — lower bound on a boolean predicate.

Q: Koko Eating Bananas -- explain binary search on the answer (LC 875).

What interviewers are really testing: Whether you can recognize “binary search on the answer” in a problem that does not mention sorting at all. This pattern appears in dozens of medium and hard problems; if you nail Koko, you can handle Capacity to Ship, Split Array Largest Sum, and Aggressive Cows.Strong Answer Framework:

Identify that the answer space (eating speed K) is monotonic: if Koko finishes at speed K, she also finishes at speed K+1.
Define the search bounds: low = 1 (smallest meaningful speed), high = max(piles) (any speed at or above this finishes in n hours).
Define the feasibility check: at speed K, total hours needed is the sum of ceil(pile / K) for each pile.
Binary search using Template 2: when feasible, try smaller (right = mid); else go bigger (left = mid + 1).
State complexity: O(n log m) where n = piles count, m = max pile size.

Real LeetCode Example — LC 875 (full code):

def minEatingSpeed(piles, h):
    def can_finish(k):
        hours = 0
        for p in piles:
            hours += (p + k - 1) // k       # ceiling division
        return hours <= h

    left, right = 1, max(piles)
    while left < right:
        mid = left + (right - left) // 2
        if can_finish(mid):
            right = mid                     # this speed works
        else:
            left = mid + 1                  # too slow -- speed up
    return left

The mental model: imagine plotting can_finish(k) for k = 1, 2, 3, … The output is a step function that goes from false, false, ..., false, true, true, ..., true. Binary search finds the transition point — the smallest k where the predicate flips to true.

Senior follow-up 1: “What if Koko could eat from multiple piles in the same hour?” Answer: the feasibility check changes because there is no per-pile rounding. Total hours needed is ceil(sum(piles) / k), a single calculation. The rest of the binary search structure stays the same. This actually makes the problem much easier — you can solve it analytically as k = ceil(sum(piles) / h).

Senior follow-up 2: “Why use ceiling division (p + k - 1) // k instead of math.ceil(p / k)?” Answer: floating-point division introduces precision errors. For very large p and small k, the result p / k may not be exactly representable as a double, and math.ceil could return one off the correct answer in edge cases. Integer ceiling is exact, branch-free, and faster.

Senior follow-up 3: “Generalize this pattern. Give two other problems that use the exact same structure.” Answer: (1) Capacity to Ship Packages within D Days (LC 1011) — search for minimum capacity, predicate is “can we ship in D days?”. (2) Minimum Number of Days to Make M Bouquets (LC 1482) — search for minimum days, predicate is “are at least M bouquets bloomable?”. (3) Magnetic Force Between Two Balls (LC 1552) — search for maximum minimum distance.

Common Wrong Answers:

“Try every speed from 1 to max(piles) and find the smallest that works.” This is O(max(piles) * n), which is way too slow when max(piles) is up to 10^9.
Setting left = 0 — causes division by zero in the feasibility check.
Setting right = sum(piles) — correct but loose, wastes iterations. max(piles) is the tight bound.
Using floating-point math in the feasibility check — precision bugs at edge cases.

Further Reading:

LC 875 (Koko Eating Bananas) — the gateway problem.
LC 1011 (Capacity to Ship Packages) — structurally identical.
LC 410 (Split Array Largest Sum) — the “minimize the maximum” version.

Q: Search in a rotated sorted array (LC 33). What if duplicates are allowed (LC 81)?

What interviewers are really testing: Your ability to identify the invariant that survives rotation (one half is always sorted) and handle the edge case where duplicates break that invariant.Strong Answer Framework:

Identify the key insight: after rotation, at least one half ([left, mid] or [mid, right]) is always sorted.
Determine which half is sorted by comparing nums[left] to nums[mid].
Check if the target falls in the sorted half’s range. If yes, search there; else search the other half.
For duplicates: when nums[left] == nums[mid] == nums[right], you cannot tell which half is sorted — shrink by one.
State complexity: O(log n) without duplicates, O(n) worst case with duplicates.

Real LeetCode Example — LC 33 (full code):

def search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return mid
        if nums[left] <= nums[mid]:                  # left half sorted
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:                                         # right half sorted
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return -1

For LC 81 with duplicates — add a guard:

def search(nums, target):
    left, right = 0, len(nums) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if nums[mid] == target:
            return True
        if nums[left] == nums[mid] == nums[right]:
            left += 1                                # cannot tell -- shrink
            right -= 1
        elif nums[left] <= nums[mid]:
            if nums[left] <= target < nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        else:
            if nums[mid] < target <= nums[right]:
                left = mid + 1
            else:
                right = mid - 1
    return False

Senior follow-up 1: “Why does the <= in nums[left] <= nums[mid] matter?” Answer: when left == mid (subarray of size 1 or 2), the “left half” is a single element and is trivially sorted. Strict < would misclassify this case and send the search to the wrong half. The = ensures that single-element subarrays are correctly considered sorted.

Senior follow-up 2: “Why does duplicates degrade to O(n)?” Answer: information-theoretically, when n-1 elements are equal and one is different, you cannot localize the different element with fewer than O(n) comparisons. Concretely, when nums[left] == nums[mid] == nums[right], both halves look identical — you cannot eliminate either with certainty. The only safe move is to shrink by one, leading to linear worst case.

Senior follow-up 3: “Could you find the minimum element in a rotated sorted array using binary search?” Answer: yes — LC 153. Compare nums[mid] with nums[right]. If nums[mid] > nums[right], the minimum is strictly to the right of mid (left = mid + 1). Else the minimum is at or to the left of mid (right = mid). This is cleaner than LC 33 because there is only one comparison branch.

Common Wrong Answers:

Trying to find the rotation point first, then doing two separate binary searches. Two passes when one suffices, and harder to get right.
Comparing nums[mid] with nums[right] instead of nums[left] (mixing conventions). Both work but you must pick one and be consistent.
Not handling the duplicates case in LC 81 — the algorithm silently produces wrong results on [1,1,3,1] searching for 3.

Further Reading:

LC 33 (Search in Rotated Sorted Array) — the source.
LC 81 (Search in Rotated Sorted Array II) — the duplicates variant.
LC 153 / 154 (Find Minimum in Rotated Sorted Array I/II) — companion problems.

Q: Median of Two Sorted Arrays in O(log(min(m,n))) (LC 4).

What interviewers are really testing: Whether you can transform a selection problem into a binary search on partition points. This is the hardest binary search problem on LeetCode and a staff-level question.Strong Answer Framework:

Recognize that the median divides all elements into two equal-sized halves — a “left half” and “right half” with the median straddling them.
Binary search for the partition point in the smaller array. The partition in the larger array is determined by it (the two partitions together must equal half the total).
The valid partition satisfies max(left half) <= min(right half), specifically A[i-1] <= B[j] and B[j-1] <= A[i].
Handle edge cases with sentinel values (-infinity and +infinity) when the partition is at an array boundary.
State complexity: O(log(min(m, n))) — always search the smaller array.

Real LeetCode Example — LC 4 (full code):

def findMedianSortedArrays(A, B):
    if len(A) > len(B):
        A, B = B, A                          # ensure A is shorter
    m, n = len(A), len(B)
    total = m + n
    half = (total + 1) // 2                  # ceiling -- for both even and odd

    left, right = 0, m
    while left <= right:
        i = (left + right) // 2              # partition in A
        j = half - i                          # partition in B

        A_left = A[i - 1] if i > 0 else float('-inf')
        A_right = A[i] if i < m else float('inf')
        B_left = B[j - 1] if j > 0 else float('-inf')
        B_right = B[j] if j < n else float('inf')

        if A_left <= B_right and B_left <= A_right:
            # valid partition
            if total % 2 == 1:
                return max(A_left, B_left)
            else:
                return (max(A_left, B_left) + min(A_right, B_right)) / 2
        elif A_left > B_right:
            right = i - 1                     # partition in A is too far right
        else:
            left = i + 1                      # partition in A is too far left

Why search the smaller array? Because j = half - i must be in [0, n]. If we search the larger array, j could go negative for small i values, requiring extra bounds checking. Searching the smaller guarantees j stays valid.

Senior follow-up 1: “Why use (total + 1) // 2 for half?” Answer: this works for both odd and even total length. For total = 5 (odd), half = 3, and the median is the maximum of the left halves. For total = 6 (even), half = 3, and the median is the average of max-of-lefts and min-of-rights. The +1 ensures the left half has the extra element when total is odd.

Senior follow-up 2: “Generalize to find the kth smallest across two sorted arrays.” Answer: change half from (total + 1) // 2 to k. The same partition-search structure finds where exactly k elements are in the combined left halves. Complexity stays O(log(min(m, n))).

Senior follow-up 3: “What if there are more than two arrays?” Answer: this exact partition technique does not extend cleanly. For K sorted arrays, use a min-heap of one element per array (O(k log k) for the median, or O(N log K) to fully merge). The two-array partition trick relies on a single binary-search axis that breaks down with more arrays.

Common Wrong Answers:

“Merge the two arrays and find the median.” O(m + n) — works but does not satisfy the O(log) requirement.
Searching the larger array instead of the smaller — invalid j indices for boundary cases.
Not using sentinel infinities for boundary partitions — causes index-out-of-bounds errors.

Further Reading:

LC 4 (Median of Two Sorted Arrays) — the source, rated Hard.
“Median of Two Sorted Arrays” by Loïc Olive — the cleanest derivation I have seen.
CLRS chapter 9 on selection algorithms.

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.

Interview Questions

Q1: Why do we write mid = left + (right - left) / 2 instead of (left + right) / 2?

What interviewers are really testing: Whether you understand machine-level integer representation and have been bitten by subtle bugs in production, or you just memorized a template without knowing why each line exists.Strong Answer:

The core issue is integer overflow. When left and right are both large values close to Integer.MAX_VALUE (2^31 - 1 in Java/C++), adding them together exceeds the 32-bit signed integer range, wrapping around to a negative number. mid then becomes negative, causing an array-out-of-bounds crash or an infinite loop.
left + (right - left) / 2 avoids this because right - left is always non-negative and smaller than right, so the intermediate value never overflows.
In Python this is technically unnecessary because Python has arbitrary-precision integers. But you should still write it this way in interviews to show awareness, and because real systems often involve C/C++/Java/Rust where it matters.
Real-world example: This was famously a bug in the Java standard library’s Arrays.binarySearch for nearly a decade (reported by Joshua Bloch in 2006). The JDK shipped with (left + right) / 2 and it only manifested on arrays with over a billion elements.
Alternatively, some people write (left + right) >>> 1 (unsigned right shift) in Java, which also works because it treats the overflow bit correctly. But left + (right - left) / 2 is clearer and portable.
Complexity: This is a constant-time operation either way; it does not change the O(log n) time or O(1) space complexity.

Red flag answer: “I just always write it that way because the template says so” or “Both are the same thing.” If you cannot explain when the naive version breaks, you are pattern-matching without understanding.Follow-ups:

“If Python handles big integers natively, can you name a language or environment where this bug would actually crash your program?” (Tests whether the candidate has written binary search outside of LeetCode, in C++/Java/Rust.)
“What is the unsigned right shift operator >>> in Java and why does it fix this problem?” (Tests bit-level understanding of two’s complement representation.)

Q2: Explain the difference between while (left <= right) and while (left < right). When do you use each?

What interviewers are really testing: Whether you truly understand binary search invariants or just memorized one template. This is the single most common source of off-by-one bugs. A candidate who can articulate this clearly almost certainly understands binary search deeply.Strong Answer:

while (left <= right) is for exact-match searches. The search space is [left, right] (closed interval). Every iteration either finds the target and returns, or shrinks the interval by moving left = mid + 1 or right = mid - 1. When left > right, the space is empty and the target does not exist.
while (left < right) is for boundary/bound searches (finding the first element that satisfies a condition). The search space is [left, right) or you converge left == right to a single answer. You typically do right = mid (not mid - 1) because mid itself might be the answer.
The gotcha with left < right: if you accidentally write right = mid - 1, you may skip the answer. If you accidentally write left = mid (without + 1), you get an infinite loop when left + 1 == right because mid equals left and nothing changes.
My mental model: left <= right means “I am still searching and have not found it yet.” left < right means “I am narrowing down to a single candidate.”
Time/Space: Both are O(log n) time, O(1) space. The difference is purely in correctness, not performance.

Red flag answer: “I always use left <= right” or inability to explain what happens when you mix the wrong loop condition with the wrong pointer update. This signals the candidate will produce subtle bugs on boundary problems.Follow-ups:

“Write a binary search that finds the leftmost occurrence of a target in a sorted array with duplicates. Which template do you use and why?” (Tests whether they can convert the conceptual understanding into code on the spot.)
“If I use while (left < right) but write left = mid instead of left = mid + 1, what exactly happens? Walk me through a concrete two-element array.” (Tests ability to trace through code and identify infinite loops.)

Q3: Search in a rotated sorted array. Walk me through your approach.

What interviewers are really testing: This is the classic “modified binary search” problem. The interviewer wants to see if you can identify which half is sorted, reason about invariants under a twist, and handle edge cases (rotation at different points, duplicates, single-element arrays). It separates people who understand binary search from people who memorized it.Strong Answer:

Key insight: Even though the array is rotated, at least one half (left or right of mid) is always sorted. We can determine which half is sorted by comparing nums[left] with nums[mid].
Algorithm:
1. Compute mid. If nums[mid] == target, return.
2. If nums[left] <= nums[mid], the left half is sorted. Check if target falls in [nums[left], nums[mid]). If yes, search left; otherwise search right.
3. Else the right half is sorted. Check if target falls in (nums[mid], nums[right]]. If yes, search right; otherwise search left.
Why <= and not < in the check? When left == mid (two-element subarray), the left “half” is just one element and is trivially sorted. Using < would incorrectly classify it and send you to the wrong half.
Edge cases to mention: Array of size 1, array not rotated at all (rotation by 0), target not present, all elements equal.
Complexity: O(log n) time, O(1) space. However, if duplicates are allowed (LeetCode 81 variant), worst case degrades to O(n) because you cannot determine which half is sorted when nums[left] == nums[mid] == nums[right].

Red flag answer: Suggesting to “find the pivot first, then do two binary searches.” While technically correct, it is an unnecessary two-pass approach. The single-pass approach shows deeper understanding. Also a red flag: not mentioning the duplicate edge case when asked.Follow-ups:

“What changes if the rotated array contains duplicates? What is the new worst-case time complexity and why?” (Tests awareness of the O(n) degenerate case and how to handle nums[left] == nums[mid].)
“Could you find the rotation point (minimum element) using binary search? How does that relate to this problem?” (Tests whether the candidate sees the connection between finding the pivot and the search problem.)

Q4: What is 'binary search on the answer' and when do you use it?

What interviewers are really testing: This is the single most important binary search concept for medium-to-hard interview problems. Many candidates only think of binary search as “search in a sorted array.” The interviewer wants to see if you can recognize the broader pattern: binary searching over a monotonic solution space.Strong Answer:

The core idea: Instead of searching for a target in an array, you binary search over the space of possible answers. For each candidate answer, you run a feasibility check (a greedy O(n) function) to determine if that answer works. Since the feasibility function is monotonic (if capacity X works, then X+1 also works), binary search applies.
Template: Define low = minimum possible answer, high = maximum possible answer. Binary search: if is_feasible(mid), try smaller (high = mid); else go bigger (low = mid + 1). Return low.
When to use it:
- “What is the minimum capacity/speed/value such that [condition]?”
- “What is the maximum X such that [condition]?”
- Any problem where brute-forcing all possible answers is too slow but checking one answer is fast.
Classic examples: Koko Eating Bananas (minimum speed), Capacity to Ship Packages (minimum capacity), Split Array Largest Sum (minimize the maximum subarray sum), Aggressive Cows (maximize minimum distance).
The hardest part is defining the search space bounds correctly. For “minimum capacity to ship,” low = max(single_weight) (you must be able to carry the heaviest item) and high = sum(all_weights) (ship everything in one day).
Complexity: O(n log R) where R is the range of the answer space and n is the cost of the feasibility check. Space is O(1).

Red flag answer: Only being able to describe binary search on arrays and not recognizing this pattern. Or defining the search bounds incorrectly (e.g., low = 0 instead of low = max(weights) in the shipping problem, which would make the feasibility check fail for impossible capacities).Follow-ups:

“In the ‘Split Array Largest Sum’ problem, you need to minimize the maximum subarray sum when splitting into k parts. Walk me through how you would set up the binary search bounds and the feasibility check.” (Tests whether the candidate can apply the pattern to a new problem in real time.)
“What happens if the feasibility function is not monotonic? Can you still use binary search on the answer? Give an example.” (Tests deep understanding of the monotonicity requirement. Answer: No, binary search requires that if f(x) is true, then f(x+1) is also true for the minimization direction.)

Q5: Find the median of two sorted arrays in O(log(min(m,n))) time.

What interviewers are really testing: This is arguably the hardest binary search problem on LeetCode (Problem 4, rated Hard). The interviewer is testing whether you can transform a selection problem into a binary search on partition points, handle edge cases with infinities, and reason about even/odd total lengths. This is a staff-level question.Strong Answer:

Key insight: The median divides all elements into two equal halves. Instead of merging the arrays (O(m+n)), we binary search for the correct partition point in the smaller array and derive the other partition from it.
Setup: Let A be the smaller array (length m), B the larger (length n). We binary search i in [0, m] representing how many elements from A go in the left half. Then j = (m + n + 1) / 2 - i elements from B go in the left half.
Invariant: For a valid partition, A[i-1] <= B[j] and B[j-1] <= A[i]. If A[i-1] > B[j], i is too big (move left). If B[j-1] > A[i], i is too small (move right).
Edge cases: When i = 0 or i = m, there are no elements on one side from A, so use negative/positive infinity for comparisons. Same for j = 0 or j = n.
Result: If total length is odd, median is max(A[i-1], B[j-1]). If even, median is (max(A[i-1], B[j-1]) + min(A[i], B[j])) / 2.
Complexity: O(log(min(m,n))) time, O(1) space. We always binary search the smaller array to minimize iterations.

Red flag answer: Suggesting O(m+n) merge as the solution (that is brute force, not what is asked). Or not knowing to binary search the smaller array. Or getting confused about the partition invariant and not being able to explain why (m + n + 1) / 2 handles both even and odd cases.Follow-ups:

“Why do we specifically binary search the smaller array and not the larger one? What changes if we searched the larger array?” (Tests understanding that searching the smaller array guarantees j stays non-negative, avoiding invalid indices.)
“How would you extend this approach to find the kth smallest element across two sorted arrays instead of the median?” (Tests generalization ability. Answer: adjust the partition sizes so the left half contains exactly k elements.)

Q6: Find a peak element in an unsorted array in O(log n) time.

What interviewers are really testing: Whether you can apply binary search to a problem that does not involve a sorted array. This tests your understanding of the deeper principle: binary search works on any space where you can eliminate half at each step, not just sorted data. Many candidates cannot see past “sorted array = binary search.”Strong Answer:

A peak element is one that is greater than its neighbors. The problem guarantees nums[-1] = nums[n] = -infinity (boundary elements are smaller than everything), which guarantees at least one peak exists.
Why binary search works here: Compare nums[mid] with nums[mid + 1]. If nums[mid] < nums[mid + 1], the right side is increasing, so a peak must exist to the right (either mid + 1 is the peak or values eventually decrease, creating a peak). Move left = mid + 1. Otherwise, the left side (including mid) contains a peak. Move right = mid.
The key insight is the “mountain guarantee”: because boundaries are -infinity, any increasing direction must eventually come back down, guaranteeing a peak. This is why we can safely discard half the array.
Template: Use while (left < right) with right = mid (not mid - 1), because mid itself could be the peak. When left == right, that index is the answer.
Complexity: O(log n) time, O(1) space. We do not find the highest peak, just any peak, which is sufficient.

Red flag answer: “You cannot use binary search on an unsorted array” (wrong, and shows rigid thinking). Or describing an O(n) linear scan (correct but misses the point of the question). Or using left <= right with right = mid - 1, which can skip the peak.Follow-ups:

“What if I asked you to find a peak in a 2D matrix where a peak is greater than all four neighbors? Can you do better than O(m*n)?” (Tests ability to extend the concept. Answer: O(m log n) or O(n log m) by applying peak finding on rows/columns iteratively.)
“Does this algorithm always find the global maximum? Why or why not?” (Answer: No. It finds a local peak. The global maximum would require O(n) in the worst case since the array is unsorted.)

Q7: Given a sorted array with duplicates, find the first and last position of a target. What is your approach?

What interviewers are really testing: Whether you understand lower bound and upper bound as distinct operations and can implement both correctly without mixing up the boundary conditions. This is a fundamental test of binary search precision. Getting it “almost right” is not good enough here because off-by-one errors surface immediately.Strong Answer:

Run two separate binary searches: one to find the leftmost occurrence (lower bound) and one to find the rightmost occurrence.
For the leftmost (lower bound): Use while (left < right). When arr[mid] >= target, set right = mid (keep searching left, mid might be the first). When arr[mid] < target, set left = mid + 1. After the loop, check if arr[left] == target.
For the rightmost (upper bound): Use while (left < right). When arr[mid] <= target, set left = mid + 1 (keep searching right). When arr[mid] > target, set right = mid. After the loop, left - 1 is the last position. Alternatively, you can use mid = left + (right - left + 1) / 2 (ceiling division) with left = mid to avoid infinite loops.
Alternatively, for the rightmost, find the upper bound (first element > target) and subtract 1. This is often cleaner: upper_bound(target) - 1.
Edge cases: target not in the array at all (return [-1, -1]), all elements are the target, target is at the boundaries.
Complexity: O(log n) time for each search, so O(log n) total. O(1) space. Much better than finding target and then linearly expanding outward, which is O(n) in the worst case when all elements are equal.

Red flag answer: “Find any occurrence then scan left and right.” This is O(n) worst case (imagine an array of all identical elements). It shows the candidate does not understand the point of binary search for bounds. Another red flag: only implementing one of the two correctly and hand-waving the other.Follow-ups:

“Can you express ‘find first occurrence’ and ‘find last occurrence’ both using a single lower_bound function with different arguments?” (Tests deeper abstraction: last occurrence of x equals lower_bound(x+1) - 1.)
“How would you count the total number of occurrences of target in O(log n)?” (Answer: upper_bound(target) - lower_bound(target). Tests whether they can compose the primitives.)

Q8: You are given a function isBadVersion(n) that tells you if version n is bad. Find the first bad version among 1 to n.

What interviewers are really testing: This is a deceptively simple problem that tests whether you can recognize the “transition point” pattern: a sorted boolean space where values go from false to true, and you need the boundary. The interviewer also wants to see if you handle the API call count concern (minimizing calls to isBadVersion, which might be expensive).Strong Answer:

This is a textbook lower-bound binary search on a boolean predicate. The “array” is conceptually [false, false, ..., false, true, true, ..., true]. We need the first true.
Use while (left < right) with right = mid (not mid - 1) because mid could be the first bad version. If isBadVersion(mid) is true, the answer is mid or earlier. If false, the answer is after mid, so left = mid + 1.
Why left <= right is wrong here: It would require a separate variable to track the answer and extra logic, making the code messier. The left < right template naturally converges to the exact transition point.
API call count: Exactly ceil(log2(n)) calls. For n = 1 billion, that is about 30 calls. If isBadVersion is a network call (e.g., checking a remote CI system), this efficiency matters.
Complexity: O(log n) time, O(1) space.

Red flag answer: Linear scan from version 1 to n (O(n) calls). Or using left <= right with right = mid - 1 and not tracking the answer separately, which would skip the first bad version.Follow-ups:

“What if isBadVersion is flaky and sometimes returns incorrect results? How would you make your search robust?” (Tests real-world thinking. Answer: call it multiple times per version and take majority vote, or use a probabilistic approach, accepting O(log n * k) calls for k repetitions.)
“What if instead of a linear version history, versions form a DAG (like git commits with branches and merges)? How would you find the first bad commit?” (Tests ability to generalize beyond arrays. This is essentially git bisect, which handles DAGs by linearizing the commit history.)

Q9: How would you apply binary search to solve Koko Eating Bananas?

What interviewers are really testing: Whether you can recognize “binary search on the answer” in a problem that does not mention arrays or sorting at all. This is the gateway problem for the entire “binary search on answer” category. If you nail this, you can handle Capacity to Ship, Split Array Largest Sum, and Aggressive Cows.Strong Answer:

Problem recap: Koko has n piles of bananas. She eats at speed k bananas/hour (one pile at a time, rounds up partial hours). Find the minimum k to finish all piles in h hours.
Why binary search applies: The answer space k is monotonic. If Koko can finish at speed k, she can definitely finish at speed k+1. So we binary search for the smallest k where can_finish(k, h) is true.
Search bounds: low = 1 (minimum meaningful speed), high = max(piles) (eating the largest pile in one hour means she finishes everything in n hours, and n <= h is guaranteed by constraints).
Feasibility check can_finish(k, h): For each pile p, the hours needed are ceil(p / k). Sum all hours. If total <= h, return true. The ceil can be computed as (p + k - 1) / k using integer math to avoid floating-point issues.
Template: while (low < high), if can_finish(mid) then high = mid, else low = mid + 1. Return low.
Complexity: O(n log m) where n = number of piles, m = max pile size. The feasibility check is O(n), and we run it O(log m) times. Space is O(1).

Red flag answer: Trying to sort the piles (irrelevant and wastes time). Or setting high = sum(piles) instead of max(piles) (technically still correct but shows lack of tight bound reasoning). Or using floating-point division in the feasibility check (introduces precision bugs).Follow-ups:

“What if Koko can eat from multiple piles in the same hour (no restriction of one pile per hour)? How does the feasibility check change?” (Tests ability to modify the greedy check. Answer: total bananas / k gives exact hours needed since no per-pile rounding.)
“Can you generalize this pattern? Give me two other problems that use the exact same structure.” (Tests pattern recognition. Good answers: Capacity to Ship Packages within D Days, Minimum Number of Days to Make m Bouquets, Magnetic Force Between Two Balls.)

Q10: You have a sorted matrix where each row and column is sorted. Find a target. What is the optimal approach?

What interviewers are really testing: There are multiple valid approaches with different trade-offs, and the interviewer wants to see if you can analyze all of them and pick the right one for the given constraints. This also tests whether you can exploit structure beyond “flat sorted array” for binary search.Strong Answer:

Clarify which type of sorted matrix: There are two common variants.
- Variant 1 (LeetCode 74): Each row is sorted, and the first element of each row is greater than the last element of the previous row. The entire matrix is one sorted sequence.
- Variant 2 (LeetCode 240): Each row is sorted left-to-right and each column is sorted top-to-bottom, but rows are NOT chained. This is the more interesting problem.
For Variant 1: Treat it as a 1D sorted array of size m * n. Binary search with index mapping: row = mid / n, col = mid % n. Time: O(log(m*n)), Space: O(1).
For Variant 2 (the staircase search): Start from the top-right corner. If the current value equals target, return true. If it is greater than target, move left (eliminate that column). If it is less, move down (eliminate that row). Each step eliminates a row or column.
Why top-right (or bottom-left)? These corners give you a decision point: one direction increases values, the other decreases. Top-left and bottom-right do not have this property (both directions increase or both decrease).
Complexity: Variant 1: O(log(m*n)) time. Variant 2: O(m + n) time. Both use O(1) space.
Can you beat O(m+n) for Variant 2? Yes, with binary search on each row: O(m log n). Or with a more advanced approach: binary search on the diagonal and then recurse on submatrices for O(m log(2n/m)) when m < n. But the staircase approach is almost always sufficient and much simpler.

Red flag answer: Only knowing the 1D flattening approach and not the staircase search (or vice versa). Or starting from the top-left corner and not being able to explain why it does not work. Or claiming O(log(m*n)) for Variant 2 without recognizing it has weaker sorting guarantees.Follow-ups:

“If I only need to check existence, the staircase approach is O(m+n). But what if I need to count all elements less than a target? Can the staircase approach help?” (Tests creative adaptation. Answer: Yes, walk the staircase and sum up column counts as you go, still O(m+n).)
“What if the matrix is very tall (m >> n)? Which approach becomes better and why?” (Tests complexity analysis. When m >> n, binary search per row O(m log n) might lose to staircase O(m + n) since n is small. But if m >> n and you can search columns, O(n log m) beats both.)

Interview Deep-Dive

You are given a problem that says 'find the minimum X such that condition C holds.' How do you recognize this as binary search on the answer, and what are the three things you must define correctly?

Strong Answer:

Recognition signal: The answer space is ordered (integers or real numbers), and the feasibility function is monotonic — if X works, then X+1 also works (for minimization). This means there is a clean boundary between “does not work” and “works,” and binary search finds that boundary.
The three things you must define:
1. Search bounds (low and high). Low = the smallest possible answer. High = the largest possible answer. Getting these wrong means you either miss the answer or search an unnecessarily large range. For “minimum speed to eat bananas in H hours”: low = 1, high = max(piles). For “minimum capacity to ship packages in D days”: low = max(weights), high = sum(weights).
2. Feasibility function is_feasible(mid). This is typically a greedy O(n) function that checks whether the candidate answer mid satisfies the constraint. For bananas: sum of ceil(pile/mid) for each pile, check if total hours is within H. For shipping: greedily pack items into days, check if days needed is within D.
3. Loop template and convergence. Use while low < high, with high = mid when feasible (try smaller) and low = mid + 1 when not. Return low. This converges to the smallest feasible value.
Common mistake: Setting low too low (e.g., low = 0 when the minimum meaningful answer is 1) causes the feasibility function to receive invalid inputs (division by zero for speed problems).
Complexity: O(n * log(range)) where n is the cost of the feasibility check and range = high - low. For integer answers, log(range) is typically 30-40 iterations.

Follow-up: What if the feasibility function is not monotonic? Can you still use binary search?

No. Binary search requires that the predicate transitions from false to true (or vice versa) exactly once. If there are multiple transitions, binary search will converge to one transition and miss the others.
If the function is non-monotonic, you need either linear search, ternary search (for unimodal functions), or a completely different approach.

What are the three binary search templates, and what is the exact off-by-one error that occurs when you mix them? Trace through a concrete two-element array.

Strong Answer:

Template 1 (exact match): while left <= right, updates left = mid + 1 and right = mid - 1. Search space is closed interval [left, right]. Returns inside the loop when found, or -1 after the loop.
Template 2 (lower bound / first true): while left < right, updates left = mid + 1 and right = mid. Search space converges to a single point. mid itself might be the answer, so we keep it in the range with right = mid.
Template 3 (upper bound / last true): while left < right, updates left = mid and right = mid - 1. Requires ceiling division for mid: mid = left + (right - left + 1) / 2 to avoid infinite loops.
The mixing error — concrete trace with [3, 5], target = 3, using Template 1 conditions with Template 2 updates:
- left=0, right=1 (should be right=len=2 for Template 2, but we used right=len-1=1).
- mid = 0. arr[0]=3 >= target, so right = mid = 0.
- left=0, right=0. Loop condition left < right is false. Return left=0. Correct by luck.
- Now target = 5: left=0, right=1. mid=0. arr[0]=3 < 5, so left = mid + 1 = 1. left=1, right=1. Loop ends. Return 1. Correct.
- But if right was initialized to len-1 instead of len and target = 6: the loop exits at left=right=1, returning 1 instead of 2 (the correct insertion point). This is the off-by-one.
The rule: Template 2’s right must be initialized to len (one past the end) because the answer might be “past all elements.” Template 1’s right is len - 1 because it searches within existing elements.

Follow-up: In practice, how do you decide which template to use for a new problem in under 30 seconds during an interview?

Ask: “Am I looking for an exact value, or a boundary?” Exact value = Template 1. First element satisfying a condition = Template 2. Last element satisfying a condition = Template 3 (or Template 2 on the complement).
If unsure, default to Template 2. It handles the most common interview scenarios and naturally converges without the right = mid - 1 trap.

Binary search in a rotated sorted array -- what is the single most common bug, and how does the presence of duplicates change the worst-case complexity from O(log n) to O(n)?

Strong Answer:

The most common bug: Using nums[left] < nums[mid] instead of nums[left] <= nums[mid] when determining which half is sorted. The = matters for two-element subarrays where left == mid. Without it, a two-element subarray [3, 1] with mid=0 would classify the left half as unsorted, sending the search to the wrong half.
How duplicates break O(log n): When nums[left] == nums[mid] == nums[right], you cannot determine which half is sorted. Consider [1, 1, 1, 1, 1, 1, 1] rotated to [1, 1, 3, 1, 1, 1, 1]. With mid pointing to a 1, both halves look identical. You cannot eliminate either half with certainty.
The only safe move with duplicates: Shrink the search space by one element: left += 1 (or right -= 1). This degrades the worst case to O(n) when all elements are equal except one.
Why this is unavoidable: Information-theoretically, if n-1 elements are the same and one is different, any comparison-based algorithm needs O(n) comparisons in the worst case to locate the different element.
Interview tip: Always ask “can the array contain duplicates?” before coding. If yes, mention the O(n) worst case explicitly.

Follow-up: If you needed to find the minimum element in a rotated sorted array with duplicates, is O(n) the best you can do?

In the worst case (all elements equal except one), yes, O(n) is optimal. No algorithm can do better.
In the average case with random data, binary search still achieves O(log n) expected time because the duplicate collision is rare.
A practical adaptive approach: when you encounter nums[left] == nums[mid], increment left by 1 and check if the next element differs. If it does, resume binary search immediately. This gives O(log n) when duplicates are sparse, degrading gracefully to O(n) only when duplicates dominate.

Overview

Array & String

Search & Sort

Data Structures

Graph & Tree

Advanced Techniques

Documentation Index

​What is Binary Search?

​Pattern Recognition Cheatsheet

​Universal Templates

​Template 1: Exact Match (left <= right)

​Template 2: Lower Bound — the canonical interview template (left < right)

​Template 3: Upper Bound (left < right with strict comparison)

​How to choose mid for upper-bound (when left = mid is needed)

​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

​Worked LeetCode Problems

​LC 704 — Binary Search (Easy)

​LC 33 — Search in Rotated Sorted Array (Medium)

​LC 153 — Find Minimum in Rotated Sorted Array (Medium)

​LC 162 — Find Peak Element (Medium)

​LC 410 — Split Array Largest Sum (Hard)

​LC 875 — Koko Eating Bananas (Medium)

​Curated LeetCode List

​Interview Q&A — Senior-Level Walkthroughs

​Practice Problems

​Practice Roadmap

​Interview Questions

​Interview Deep-Dive

What is Binary Search?

Pattern Recognition Cheatsheet

Universal Templates

Template 1: Exact Match (`left <= right`)

Template 2: Lower Bound — the canonical interview template (`left < right`)

Template 3: Upper Bound (`left < right` with strict comparison)

How to choose mid for upper-bound (when `left = mid` is needed)

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

Worked LeetCode Problems

LC 704 — Binary Search (Easy)

LC 33 — Search in Rotated Sorted Array (Medium)

LC 153 — Find Minimum in Rotated Sorted Array (Medium)

LC 162 — Find Peak Element (Medium)

LC 410 — Split Array Largest Sum (Hard)

LC 875 — Koko Eating Bananas (Medium)

Curated LeetCode List

Interview Q&A — Senior-Level Walkthroughs

Practice Problems

Practice Roadmap

Interview Questions

Interview Deep-Dive