Backend Study Lab

Algorithms

Binary Search Explained

Learn how binary search works, when it applies, common off-by-one mistakes, and how to implement iterative binary search in Java.

By CloveCode Studio Jun 28, 2026 Updated Jul 5, 2026 4 min read

Quick answer

Binary search is an algorithm for finding a target value in a sorted search space. Instead of checking every element, it repeatedly compares the target with the middle value and discards half of the remaining candidates.

For a sorted array with n elements, binary search runs in O(log n) time and uses O(1) extra space in the iterative version.

When binary search works

Binary search needs a monotonic condition. The common case is a sorted array:

[2, 5, 8, 12, 16, 23, 38, 56]

If the target is smaller than the middle value, it cannot be in the right half. If the target is larger, it cannot be in the left half.

The same idea works beyond arrays when the problem has a true or false boundary. For example, “what is the first version that fails?” or “what is the smallest capacity that can finish this work?” can often be solved with binary search on an answer range.

Binary search step by step

Search for 23 in this sorted array:

index:  0   1   2   3   4   5   6   7
value: [2,  5,  8, 12, 16, 23, 38, 56]

Start with the full range:

left = 0
right = 7
mid = 3
value = 12

The target 23 is greater than 12, so everything at index 3 and below can be ignored. Move left to 4.

Now search indexes 4 through 7:

left = 4
right = 7
mid = 5
value = 23

The middle value is the target, so the search returns index 5.

Java implementation

A basic iterative implementation looks like this:

public static int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] == target) {
            return mid;
        }

        if (nums[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;
}

The expression left + (right - left) / 2 avoids integer overflow that can happen with (left + right) / 2 when indexes are very large.

Why the loop uses left less than or equal to right

The condition left <= right means the current range is inclusive on both sides. When left and right point to the same index, there is still one candidate left to check.

If the loop used only left < right, the implementation would need different update rules and a separate final check. That can work, but mixing inclusive and exclusive boundaries is a common source of bugs.

Pick one boundary style and stay consistent.

Time complexity

Binary search cuts the remaining search space roughly in half each step:

n -> n / 2 -> n / 4 -> n / 8 -> ...

The number of steps grows logarithmically, so the time complexity is O(log n). If an array has about one million elements, binary search needs around 20 comparisons in the worst case.

Read Big-O Notation Explained for the reasoning behind logarithmic growth, or use the Big-O Cheat Sheet as a quick reference.

Common mistakes

The first mistake is using binary search on unsorted data. If the values are not sorted and there is no monotonic condition, discarding half of the search space is not valid.

The second mistake is updating the wrong boundary:

left = mid;  // often wrong in inclusive binary search

If left already equals mid, this can create an infinite loop. In the inclusive array search version, move past the middle with left = mid + 1 or right = mid - 1.

The third mistake is returning any match when the problem asks for the first or last occurrence. A normal binary search can find a matching value, but duplicates require a modified version.

First occurrence with duplicates

When the array can contain duplicates, you may need the first index where the target appears.

public static int firstIndexOf(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    int answer = -1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (nums[mid] >= target) {
            if (nums[mid] == target) {
                answer = mid;
            }
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    return answer;
}

This version keeps searching left after finding the target, because an earlier duplicate may still exist.

Binary search on answers

Some backend and interview problems do not search an array directly. They search for the smallest value that satisfies a condition.

Example problem shape:

Find the smallest batch size that can process all jobs within 60 minutes.

If batch size 100 works, then larger batch sizes probably work too. If batch size 20 does not work, smaller batch sizes probably do not work. That monotonic true or false boundary is what binary search needs.

Boundary checklist

Most binary search bugs are boundary bugs. Before committing an implementation, write down whether the interval is inclusive (left <= right) or half-open (left < right). Then verify that every branch moves the boundary and that the loop cannot repeat the same left, right, and mid values forever.

For answer-search problems, test the smallest valid answer, the largest valid answer, and a case where no answer exists. The monotonic condition should be isolated in a helper such as canProcess(batchSize), because that makes it easier to test the condition separately from the search mechanics.

Read Big-O Notation Explained for the complexity model behind binary search. For adjacent array patterns, read Two Pointers Algorithm Explained, Sliding Window Algorithm Explained, and Prefix Sum Algorithm Explained. For Java collection lookup tradeoffs, read Time Complexity of Java Collections. Use the Big-O Cheat Sheet when comparing O(n), O(log n), and O(n log n) behavior. For the full sequence, browse the Algorithms and Complexity Learning Path.

Keep reading