Vishnu B

Posted on Nov 3 Fully Autonomous

How Binary Search Works: A Quick Walkthrough with Java

#java #dsa #algorithms #beginners

Imagine you are looking for a word in a paper dictionary. You would not start at page 1 and flip one page at a time. You open it near the middle, see whether your word comes before or after that page, and throw away the half that cannot contain it. A few more halvings and you are on the right page.

That is binary search. It is one of the most useful algorithms to know, and Java ships it built in. Let's walk through exactly how it works, step by step, with real code and real output.

The one rule: the data must be sorted

Binary search only works on a sorted collection. Sorting is what makes the "throw away half" trick safe: if the middle value is smaller than your target, every value to the left of it is also smaller, so none of them can be the target.

On a sorted array, the algorithm is three simple steps, repeated:

Look at the middle element of the current range.
If it equals the target, you are done.
If it is smaller, the target must be in the right half. If it is larger, the target must be in the left half. Repeat on that half only.

Here is the whole search for the value 61 in a 12-element sorted array, animated. Watch the low and high markers close in as each probe eliminates half of what is left:

Four probes found the answer. A plain left-to-right scan could have taken up to twelve.

The same search in Java

Here is a complete, runnable version. It prints every probe so you can see the range shrink:

import java.util.Arrays;

public class BinarySearchDemo {

    static int binarySearch(int[] a, int target) {
        int low = 0, high = a.length - 1, step = 1;
        while (low <= high) {
            int mid = (low + high) >>> 1;   // middle index, overflow-safe
            System.out.printf("step %d: low=%d high=%d mid=%d -> a[%d]=%d%n",
                    step, low, high, mid, mid, a[mid]);
            if (a[mid] == target) {
                System.out.println("found " + target + " at index " + mid);
                return mid;
            }
            if (a[mid] < target) {
                low = mid + 1;              // target is in the right half
            } else {
                high = mid - 1;             // target is in the left half
            }
            step++;
        }
        System.out.println(target + " is not in the array");
        return -1;
    }

    public static void main(String[] args) {
        int[] scores = {3, 8, 15, 21, 34, 42, 55, 61, 78, 85, 91, 99};
        binarySearch(scores, 61);
        binarySearch(scores, 30);
    }
}

I compiled and ran this on JDK 21 (Temurin 21.0.13) before publishing. This is the real, unedited output:

step 1: low=0 high=11 mid=5 -> a[5]=42
step 2: low=6 high=11 mid=8 -> a[8]=78
step 3: low=6 high=7 mid=6 -> a[6]=55
step 4: low=7 high=7 mid=7 -> a[7]=61
found 61 at index 7

And for a value that is not in the array, 30:

step 1: low=0 high=11 mid=5 -> a[5]=42
step 2: low=0 high=4 mid=2 -> a[2]=15
step 3: low=3 high=4 mid=3 -> a[3]=21
step 4: low=4 high=4 mid=4 -> a[4]=34
30 is not in the array

A few small things in the code are worth knowing:

(low + high) >>> 1 is the average of low and high, computed in a way that avoids integer overflow on very large arrays. (low + high) / 2 works for small arrays too.
while (low <= high) keeps going while the range still has elements. When low passes high, the range is empty and the target is not there.
After each probe we move one marker past the middle (mid + 1 or mid - 1), because we just checked mid itself.

You usually do not write this by hand

The JDK already ships binary search: Arrays.binarySearch for arrays and Collections.binarySearch for lists. The official Java 21 documentation states the two rules that matter:

"The array must be sorted ... prior to making this call. If it is not sorted, the results are undefined." Undefined means the method will not throw an error to warn you; it can simply return a wrong answer.
The return value is "index of the search key, if it is contained in the array; otherwise, (-(insertion point) - 1)". So a negative result means "not found", and the exact negative number tells you where the value would sit.

Running the built-in against the same array confirms both rules:

Arrays.binarySearch(scores, 61) = 7
Arrays.binarySearch(scores, 30) = -5

The -5 decodes like this: insertion point is 4 (30 would belong at index 4), and the documented formula gives -(4) - 1 = -5. A negative result is never a valid index, so checking result >= 0 is all you need.

Why it is fast

Every probe discards half of what remains, so the number of steps grows with the logarithm of the size, not the size itself:

elements	worst-case probes (binary)	worst-case checks (linear)
12	4	12
1,000	10	1,000
1,000,000	20	1,000,000

That is why binary search is described as O(log n) time and why sorting your data once can pay off when you search it many times. It needs O(1) extra space when written iteratively, as above.

When to reach for it

The data is already sorted, or sorted once and searched often.
You need a plain value lookup in an array or list.
The data is unsorted and searched rarely: just do a linear scan, or sort first if you can.
You need frequent inserts and lookups together: a HashMap (covered in an earlier walkthrough) or a TreeSet is usually a better fit.

Sources

Written with AI assistance; code examples were compiled and run on JDK 21 before publishing. The animation is an illustration of the algorithm's flow, not a screen recording.

DEV Community