The Binary Search Playbook: Every Variation You'll Ever See in Interviews

Binary search sounds simple. "Search a sorted array in O(log n)." Every student knows that. Yet binary search problems have one of the highest failure rates in interviews — even among students who've solved hundreds of problems.

The reason: there are dozens of variations, and each one breaks the naive implementation in a subtle way. Off-by-one errors, infinite loops, and wrong comparisons are incredibly easy to introduce.

This guide gives you one correct template and then shows you exactly how to adapt it for every variation.

---

Why Binary Search is Hard to Get Right

Consider this: for the classic binary search, there are 4 decisions that can each go wrong independently:

1. Loop condition: while left < right or while left <= right?
2. Midpoint: mid = (left + right) // 2 or mid = left + (right - left) // 2?
3. Left update: left = mid or left = mid + 1?
4. Right update: right = mid or right = mid - 1?

That's 16 combinations for basic binary search. Only a few are correct. The rest cause either wrong answers or infinite loops.

The solution: commit to one template and understand why every choice is made.

---

The Master Template

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2  # prevents integer overflow
        
        if arr[mid] == target:
            return mid
        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  # target not found

Every decision justified:

• left <= right: We need to check when left == right (single element). Using < would skip it.
• mid = left + (right - left) // 2: Equivalent to (left + right) // 2 but avoids integer overflow for large arrays. Always use this form.
• left = mid + 1: We already checked mid and it's not the target. Don't recheck it.
• right = mid - 1: Same reasoning — don't recheck mid.

Memorise this. Every variation below is a controlled modification of this base.

---

Variation 1: Find First Occurrence

Given a sorted array with possible duplicates, find the index of the first occurrence of target. Return -1 if not found.

def find_first(arr, target):
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            result = mid        # found one — but keep searching left
            right = mid - 1    # ← key change: narrow right to find earlier occurrence
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result

Key insight: When you find the target, don't stop. Record it as a candidate answer, then keep searching the left half for an earlier occurrence.

---

Variation 2: Find Last Occurrence

def find_last(arr, target):
    left, right = 0, len(arr) - 1
    result = -1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            result = mid        # found one — but keep searching right
            left = mid + 1     # ← key change: narrow left to find later occurrence
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    
    return result

Combining both: LeetCode "Find First and Last Position" = [find_first(arr, target), find_last(arr, target)]. Two separate binary searches.

---

Variation 3: Find Insertion Position

Find the index where target should be inserted to keep the array sorted (even if target doesn't exist).

def search_insert(arr, target):
    left, right = 0, len(arr)  # ← right = len(arr), not len(arr)-1
    
    while left < right:         # ← strict less-than
        mid = left + (right - left) // 2
        
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid          # ← right = mid, not mid - 1
    
    return left

Why different? We're no longer searching for an element — we're finding a position. The invariant is: left is always a valid insertion point. When the loop ends, left == right is the answer.

This is also Python's bisect_left behavior.

---

Variation 4: Search in Rotated Sorted Array

A sorted array has been rotated at an unknown pivot (e.g., [4,5,6,7,0,1,2]). Find the index of target.

This is a classic medium problem. The key insight: even in a rotated array, one half is always sorted.

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

Trace through [4,5,6,7,0,1,2], target=0:

• left=0, right=6, mid=3, nums[3]=7
• nums[0]=4 ≤ nums[3]=7 → left half sorted
• Is 4 ≤ 0 < 7? No → left = mid + 1 = 4
• left=4, right=6, mid=5, nums[5]=1
• nums[4]=0 ≤ nums[5]=1 → left half sorted
• Is 0 ≤ 0 < 1? Yes → right = mid - 1 = 4
• left=4, right=4, mid=4, nums[4]=0 == target → return 4 ✓

---

Variation 5: Find Minimum in Rotated Sorted Array

Find the minimum element in a rotated sorted array.

def find_min_rotated(nums):
    left, right = 0, len(nums) - 1
    
    while left < right:  # ← stops when left == right (one element)
        mid = left + (right - left) // 2
        
        if nums[mid] > nums[right]:
            # Minimum is in the right half (not mid)
            left = mid + 1
        else:
            # Minimum is in the left half (could be mid)
            right = mid   # ← don't exclude mid
    
    return nums[left]

Why compare to nums[right] not nums[left]? If nums[mid] > nums[right], the rotation point (minimum) must be in [mid+1, right]. If nums[mid] <= nums[right], minimum is in [left, mid].

---

Variation 6: Binary Search on the Answer Space

This is the most powerful and underused binary search technique. Instead of searching an array, you search the space of possible answers.

Pattern: When a problem asks "find the minimum/maximum X such that condition Y is satisfied."

Example: Koko Eating Bananas

Koko can eat at most k bananas/hour. She has h hours. Find the minimum k that lets her eat all piles.

def min_eating_speed(piles, h):
    def can_finish(speed):
        hours_needed = sum((pile + speed - 1) // speed for pile in piles)
        return hours_needed <= h
    
    left, right = 1, max(piles)   # answer must be in [1, max_pile]
    
    while left < right:
        mid = left + (right - left) // 2
        
        if can_finish(mid):
            right = mid      # mid works — try smaller speed
        else:
            left = mid + 1   # mid doesn't work — need faster speed
    
    return left

The template for "search on answer":

left, right = minimum_possible_answer, maximum_possible_answer

while left < right:
    mid = left + (right - left) // 2
    
    if feasible(mid):
        right = mid       # mid works, try smaller
    else:
        left = mid + 1    # mid doesn't work, try larger

return left

More problems using this template:

• Minimum Days to Make m Bouquets: Binary search on number of days
• Capacity to Ship Packages in D Days: Binary search on ship capacity
• Find the Smallest Divisor Given a Threshold: Binary search on divisor

---

Variation 7: Find Peak Element

A peak element is an element greater than its neighbours. Find any peak in O(log n).

def find_peak(nums):
    left, right = 0, len(nums) - 1
    
    while left < right:
        mid = left + (right - left) // 2
        
        if nums[mid] > nums[mid + 1]:
            # Descending — peak is at mid or to its left
            right = mid
        else:
            # Ascending — peak is to the right of mid
            left = mid + 1
    
    return left

---

When to Use Binary Search: The Decision Checklist

Binary search applies when you have monotonicity — a function that transitions from False to True (or True to False) exactly once.

Ask yourself:

1. Is the data sorted? → Standard binary search
2. Is there a rotated sorted array? → Variation 4 or 5
3. Does the problem ask for first/last of something? → Variation 1 or 2
4. Does the problem ask for minimum/maximum X such that some condition holds? → Binary search on answer space
5. Does the problem have a clear "feasibility" function and a bounded answer range? → Binary search on answer space

---

Common Bugs and How to Avoid Them

| Bug | Symptom | Fix | |---|---|---| | right = len(arr) instead of len(arr)-1 | Index out of bounds | Use len(arr)-1 for element search | | mid = (left + right) // 2 | Integer overflow (rare in Python) | Use left + (right - left) // 2 | | left = mid instead of mid + 1 | Infinite loop | Always use mid + 1 when moving left pointer past mid | | right = mid instead of mid - 1 in standard search | Infinite loop or wrong answer | Use mid - 1 in standard search; mid only when searching for position | | Not handling empty array | Crash or wrong output | Check if not arr: return -1 before starting |

---

Practice Problems by Difficulty

Easy (get these perfect first):

• Binary Search (LeetCode #704)
• Search Insert Position (#35)
• First Bad Version (#278)

Medium (the real interview questions):

• Find First and Last Position (#34)
• Search in Rotated Sorted Array (#33)
• Find Minimum in Rotated Sorted Array (#153)
• Koko Eating Bananas (#875)
• Capacity to Ship Packages (#1011)

Hard (differentiate yourself):

• Median of Two Sorted Arrays (#4)
• Split Array Largest Sum (#410)

Start now: Open Practice and filter by "Binary Search". Solve the Easys today with the template above — resist looking at solutions until you've tried for 20 minutes.