# Key Considerations for Implementing Binary Search Correctly

> 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.

- Repository: [DonglaiFu/fucking-algorithm](https://github.com/labuladong/fucking-algorithm)
- Tags: how-to-guide
- Published: 2026-02-25

---

**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.

```java
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.

```java
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.

```java
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.