Key Considerations for Implementing Binary Search Correctly

Question

Master binary search implementation with this guide. Learn interval choices, midpoint calculation to avoid overflow, and pointer updates for accuracy. Get it right every time.

Accepted Answer

To implement binary search correctly, you must choose between closed [left, right] and half-open [left, right) intervals, calculate the midpoint with left + (right - left) / 2 to prevent integer overflow, and ensure pointer updates strictly match your interval definition to avoid infinite loops or skipped elements.

The repository labuladong/fucking-algorithm dedicates its comprehensive guide 算法思维系列/二分查找详解.md to demystifying the subtle bugs that break binary search implementations. Mastering the key considerations for implementing binary search correctly ensures your algorithm terminates reliably and returns accurate indices across all edge cases. This article extracts the repository's battle-tested patterns into concrete implementation rules with full code examples.

Define Your Search Interval: Closed vs. Half-Open

The first architectural decision is choosing your interval model, which dictates every subsequent line of code. In the closed interval model [left, right], the search space includes both endpoints, requiring a loop condition of while (left <= right) and termination when left > right. The half-open model [left, right) excludes the right endpoint, uses while (left < right), and terminates when left == right.

According to 算法思维系列/二分查找详解.md (lines 60-71), mismatched conditions and updates cause off-by-one errors that either miss targets or run forever. Select one model and apply it consistently throughout the algorithm.

Calculate the Midpoint Without Integer Overflow

Directly computing mid = (left + right) / 2 risks integer overflow when indices approach Integer.MAX_VALUE. The robust formula mid = left + (right - left) / 2 guarantees correctness across the entire integer range.

As noted in the repository's §"计算 mid 时需要防止溢出" (line 82), this adjustment is essential for production code handling large datasets or high-index arrays.

Update Pointers to Shrink the Interval Correctly

Pointer updates must strictly exclude the already-checked mid element to guarantee progress. For closed intervals [left, right], use left = mid + 1 and right = mid - 1. For half-open intervals [left, right), use left = mid + 1 and right = mid.

Incorrect updates either re-include mid—causing infinite loops—or skip valid candidates, as detailed in §"为什么是 left = mid + 1，right = mid - 1？" (lines 83-91).

Distinguish the Three Binary Search Goals

The repository identifies three distinct search objectives, each requiring different handling of the nums[mid] == target case. The implementation strategy changes based on whether you need any match, the first match, or the last match.

Find Any Occurrence (Standard Binary Search)

When searching for any matching index, return immediately upon finding the target. This is the simplest variant using a closed interval.

int binarySearch(int[] nums, int target) {
    int left = 0, right = nums.length - 1;          // closed interval
    while (left <= right) {                         // condition matches interval
        int mid = left + (right - left) / 2;        // overflow-safe
        if (nums[mid] == target) return mid;       // immediate success
        else if (nums[mid] < target) left = mid + 1;
        else /* nums[mid] > target */ right = mid - 1;
    }
    return -1;                                      // not found
}

Source: Lines 94-115 of 算法思维系列/二分查找详解.md.

Find Left Boundary (First Occurrence)

To find the first occurrence, shrink the right boundary even when nums[mid] == target to continue searching for earlier matches. Post-loop validation ensures the target actually exists at the returned index.

int leftBound(int[] nums, int target) {
    int left = 0, right = nums.length;              // half-open [0, n)
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) left = mid + 1;     // discard left part
        else right = mid;                           // keep mid for possible earlier match
    }
    // post-process: verify existence
    return (left < nums.length && nums[left] == target) ? left : -1;
}

Source: Lines 13-33 of the "寻找左侧边界的二分搜索" section.

Find Right Boundary (Last Occurrence)

To find the last occurrence, shrink the left boundary when nums[mid] == target to continue searching for later matches, then convert the final pointer to the actual index.

int rightBound(int[] nums, int target) {
    int left = 0, right = nums.length;              // half-open interval
    while (left < right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] > target) right = mid;        // discard right part
        else left = mid + 1;                        // keep mid if equal, move right
    }
    // left is now first index > target
    int idx = left - 1;
    return (idx >= 0 && nums[idx] == target) ? idx : -1;
}

Source: Lines 34-56 of the "寻找右侧边界的二分查找" section.

Validate Results and Handle Edge Cases

After the loop terminates, verify that the candidate index actually contains the target, especially for boundary searches that return insertion points rather than confirmed matches. For empty inputs, return -1 immediately before computing boundaries to prevent right = -1 and subsequent mid calculation errors.

The repository emphasizes explicit else if chains over generic else clauses to prevent hidden control-flow bugs (§"分析二分查找的一个技巧是：不要出现 else，而是把所有情况用 else if 写清楚", lines 78-80). This explicit structure makes the three-way branching clear and auditable.

Summary

Choose an interval model—closed [left, right] or half-open [left, right)—and match your loop condition (<= vs <) and pointer updates to it.
Calculate mid safely using left + (right - left) / 2 to avoid integer overflow near Integer.MAX_VALUE.
Update pointers to strictly exclude checked elements: mid ± 1 for closed intervals, mid for half-open right boundaries.
Distinguish search goals: return immediately for any occurrence, or shrink the interval progressively for left/right boundaries.
Validate results after the loop and guard against empty arrays before processing to prevent out-of-bounds returns.

Frequently Asked Questions

Why does my binary search implementation get stuck in an infinite loop?

An infinite loop occurs when pointer updates fail to shrink the interval, typically by setting right = mid in a closed interval [left, right] or using <= with right = mid without the -1 offset. Ensure updates strictly exclude the mid element already compared to guarantee forward progress.

What is the difference between closed and half-open intervals in binary search?

A closed interval [left, right] includes both endpoints and requires while (left <= right) with updates left = mid + 1 and right = mid - 1. A half-open interval [left, right) excludes right, uses while (left < right), and updates right = mid when discarding the right side.

How do I find the first or last occurrence of a target instead of any occurrence?

For the left boundary, shrink right when nums[mid] == target to continue searching left for an earlier match. For the right boundary, shrink left when equal to continue searching right. Always post-process the final index to confirm the target exists, as these variants return insertion positions when the target is absent.

Why use `left + (right - left) / 2` instead of `(left + right) / 2`?

The expression (left + right) can overflow when both indices are large positive integers near Integer.MAX_VALUE, producing a negative midpoint and array access errors. The formula left + (right - left) / 2 computes the same midpoint using subtraction first, avoiding overflow entirely.