Master Binary Search with a Magic Template: Tips, Pitfalls & LeetCode Examples

Introduction

The author shares a binary‑search template that he has refined over six months of LeetCode practice, highlighting its advantages, usage tips, common pitfalls, and debugging methods.

Historical background

Although the basic idea of binary search is straightforward, the details can be surprisingly tricky – Donald Knuth.

Knuth also noted that the first bug‑free binary search appeared only in 1962, and that a similar bug persisted in Java's JDK for about a decade.

Problems with the traditional binary‑search template

(1) Mid‑index calculation can overflow int mid = (left + right) / 2; When left and right are large, left + right may exceed the maximum int value, causing overflow. The safer form is: int mid = left + (right - left) / 2; Even this can overflow in extreme cases, so the author recommends using an unsigned right‑shift: int mid = (left + right) >>> 1; (2) Loop condition and return value

Using while (left <= right) makes it easy to forget whether to return left or right after the loop, leading to off‑by‑one errors, especially for LeetCode 35 (search insert position).

"Magic" binary‑search template

The core ideas are:

Use while (left < right) as the loop condition; when the loop exits, left == right.

Return either left or right directly if the target is guaranteed to be in the range; otherwise perform a final check (post‑processing).

Choose the mid‑index based on branch logic to avoid dead loops when only two elements remain.

Typical mid‑index calculation:

int mid = (left + right) >>> 1;

Reference implementations

public class Solution {
    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) return 0;
        int left = 0;
        int right = len; // exclusive upper bound
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

public class Solution2 {
    public int searchInsert(int[] nums, int target) {
        int len = nums.length;
        if (len == 0) return -1;
        if (nums[len - 1] < target) return len;
        int left = 0;
        int right = len - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return right;
    }
}

Details, pitfalls and debugging

Boundary selection must include the target; for example, in LeetCode 69 (square root) the left bound is 0 and the right bound is x.

When the interval shrinks to two elements, choose left‑mid or right‑mid according to which side can safely discard the mid element to avoid infinite loops.

Print left, right, mid, and the target when debugging a loop that does not terminate.

If the target may be absent (e.g., LeetCode 704), perform a final check on nums[left] after the loop.

Conclusion

The "magic" binary‑search template reduces the number of branches to two, eliminates the need to test the mid element on every iteration, and, when combined with proper boundary handling and unsigned right‑shift mid calculation, avoids overflow and dead‑loop bugs. Applying this template to various LeetCode problems solidifies understanding and improves coding speed.