Binary Search Mastery: Avoid the Three Most Common Infinite Loop Bugs

Here is the version most people write from memory:

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

This is the standard template — and for a simple "find the exact value" problem, it works perfectly. The loop terminates because every iteration either returns or shrinks the search window by at least one element. But the moment the problem changes slightly — find the leftmost occurrence, find the insertion point, or operate on an implicit answer space — developers start reaching for a slightly different template, and that is where the bugs creep in.

Understanding the Infinite Loop Root Cause

An infinite loop in binary search happens when mid equals either left or right, and the loop boundary does not move. Consider this buggy variant:

# BUGGY — can loop forever
def find_leftmost(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:          # note: strictly less-than
        mid = (left + right) // 2
        if nums[mid] < target:
            left = mid + 1
        else:
            right = mid           # right does NOT move past mid
    return left

When left = 0 and right = 1, Python's integer division gives mid = 0. If nums[0] >= target, we set right = mid = 0. Now left == right == 0, the condition left < right is False, and we exit. That actually works — but it only works because Python's // rounds down. The instant you use mid = (left + right + 1) // 2 (ceiling division), you must also adjust which boundary gets set to mid, otherwise you spin forever.

The Two Safe Templates You Must Memorize

There are exactly two safe, proven binary search templates. Once you internalize them, you will never write an infinite loop again.

Template 1 — Floor (left-biased mid)

left, right = 0, n - 1
while left < right:
    mid = (left + right) // 2      # floor: biased toward left
    if condition(mid):
        right = mid                # mid could be the answer, keep it
    else:
        left = mid + 1             # mid is definitely wrong, skip it
# loop exits with left == right == answer

Use this when you are searching for the leftmost valid position. Because mid is always strictly less than right when left < right, setting right = mid guarantees progress.

Template 2 — Ceiling (right-biased mid)

left, right = 0, n - 1
while left < right:
    mid = (left + right + 1) // 2  # ceiling: biased toward right
    if condition(mid):
        left = mid                 # mid could be the answer, keep it
    else:
        right = mid - 1            # mid is definitely wrong, skip it
# loop exits with left == right == answer

Use this when you are searching for the rightmost valid position. The +1 ensures mid > left when the window has two elements, so setting left = mid still makes progress.

The Integer Overflow Trap

In Python you never worry about this, but in Java, C++, or any language with fixed-width integers, the classic line mid = (left + right) / 2 is a time bomb. When left and right are both near INT_MAX, their sum overflows to a negative number, and your mid-point is suddenly in the wrong half of the array.

The idiomatic fix that every interviewer wants to see:

// Java — overflow-safe
int mid = left + (right - left) / 2;

// C++ — overflow-safe
int mid = left + (right - left) / 2;

This is mathematically equivalent to (left + right) / 2 but avoids the intermediate overflow. Writing it this way in an interview signals that you understand low-level constraints — a major green flag for interviewers.

Binary Search on Answer Space

Many interview problems are not obviously binary search problems. The array is not given to you directly — instead, the problem has a monotonic predicate that you binary search over an implicit range. Classic examples include:

• Koko Eating Bananas (LeetCode 875) — Binary search over eating speed.
• Minimum Speed to Arrive on Time (LeetCode 1870) — Binary search over speed values.
• Capacity To Ship Packages (LeetCode 1011) — Binary search over ship weight capacity.
• Find the Smallest Divisor (LeetCode 1283) — Binary search over divisor values.

The pattern is always the same: define a feasible(x) function that returns True for all values above (or below) a threshold, then binary search for that threshold. The entire search space is just a range of integers, not an actual array.

# Template for "minimum value that satisfies condition"
def solve(nums, limit):
    def feasible(capacity):
        # your O(n) check here
        ...

    left, right = min_possible, max_possible
    while left < right:
        mid = (left + right) // 2
        if feasible(mid):
            right = mid
        else:
            left = mid + 1
    return left

Common Interview Mistakes and How to Avoid Them

Mistake	Root Cause	Fix
Infinite loop	mid == left or right, boundary doesn't move	Use the correct ceiling/floor template consistently
Off-by-one on return value	Returning left vs right vs left-1	Trace through a 2-element example before submitting
Wrong initial bounds	right = n vs right = n-1	Think about whether the answer could be at index n
Integer overflow	(left+right)/2 in Java/C++	left + (right-left)/2
Not verifying termination	Trusting intuition over proof	Always trace a 2-element window manually

Practice Problems — Ordered by Difficulty

Here is a curated list to take you from beginner to expert level:

1. LeetCode 704 — Binary Search (basic, warm-up)
2. LeetCode 35 — Search Insert Position (leftmost template)
3. LeetCode 34 — Find First and Last Position (both templates combined)
4. LeetCode 153 — Find Minimum in Rotated Sorted Array
5. LeetCode 33 — Search in Rotated Sorted Array
6. LeetCode 875 — Koko Eating Bananas (answer space)
7. LeetCode 1011 — Capacity To Ship Packages (answer space)
8. LeetCode 410 — Split Array Largest Sum (hard, answer space)

What Interviewers Actually Want to See

When you code binary search in a real interview, the evaluator is watching for three things beyond just "does it compile":

1. Clarity of invariant. Can you articulate what left and right represent at every point in the loop? Strong candidates say things like "left is the smallest index I haven't yet ruled out" rather than just writing code.
2. Termination proof. Can you explain in one sentence why the loop always terminates? "Because each iteration either returns or shrinks the window" is the answer.
3. Edge case awareness. Empty array, single element, all elements equal, target not present — mention these proactively, even if you don't code all of them explicitly.

Key Takeaways

• Two templates, not one: floor mid → right = mid for leftmost, ceiling mid → left = mid for rightmost.
• Never mix ceiling mid with right = mid — that combination can infinite loop.
• In Java/C++, always use left + (right - left) / 2.
• Binary search applies to any monotonic predicate, not just sorted arrays.
• Trace a 2-element window before every submission — it catches 90% of off-by-one errors.

Binary search mastery is not about memorizing a single piece of code — it is about deeply understanding why each line exists. Once you internalize the two templates and can justify every decision, you will handle any variant an interviewer throws at you. Happy coding!