Binary Search in Java

Think of finding a word in a printed dictionary. You don't start at page 1. You open somewhere in the middle, see that your word comes later, and ignore the whole first half. Then you do it again with the half that is left. In a few flips you are on the right page, even in a book with a thousand pages. Binary search is that idea written as code. In this lesson, you will learn how binary search works, write it in Java both with a loop and with recursion, see why it takes only O(log n) steps, and use the JDK's ready-made version.

What Is Binary Search?

Binary search in Java is a searching algorithm that is used to find a target in a sorted array by repeatedly comparing the target with the middle element and throwing away the half that can't contain it.

• The data must be sorted. On unsorted data, binary search gives wrong answers.
• Each step halves the range, so it needs at most about log₂ n steps.
• It returns the index of the target, or a "not found" result.

How It Works

1. Keep two indexes: low (start of the range) and high (end of the range).
2. Find the middle: mid = low + (high - low) / 2.
3. If values[mid] equals the target, you are done.
4. If values[mid] is less than the target, the target can only be to the right: set low = mid + 1.
5. If it is greater, set high = mid - 1.
6. Repeat while low <= high. If the range becomes empty, the target isn't there.

Iterative Binary Search

Let's see an example that prints each step for the search in the picture.

public class BinarySearch {
    static int binarySearch(int[] values, int target) {
        int low = 0;
        int high = values.length - 1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            System.out.println("  low=" + low + " high=" + high
                    + " mid=" + mid + " value=" + values[mid]);
            if (values[mid] == target) {
                return mid;
            } else if (values[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
 
    public static void main(String[] args) {
        int[] marks = {3, 8, 15, 21, 27, 34, 42, 56, 63, 71};
        System.out.println("Search 63 -> index " + binarySearch(marks, 63));
        System.out.println("Search 20 -> index " + binarySearch(marks, 20));
    }
}

  low=0 high=9 mid=4 value=27
  low=5 high=9 mid=7 value=56
  low=8 high=9 mid=8 value=63
Search 63 -> index 8
  low=0 high=9 mid=4 value=27
  low=0 high=3 mid=1 value=8
  low=2 high=3 mid=2 value=15
  low=3 high=3 mid=3 value=21
Search 20 -> index -1

Explanation:

1. The search for 63 takes 3 steps, exactly as in the picture.
2. The search for 20 narrows the range until low passes high, then returns -1. It needed 4 steps to prove the value is missing; linear search would need 10.
3. low + (high - low) / 2 is used instead of (low + high) / 2. For very large arrays, low + high can be bigger than the largest int and overflow into a negative number. This exact bug sat in the JDK's own binary search for years.

Recursive Binary Search

The same algorithm can be written recursively: search the half that is left by calling the method again.

public class RecursiveSearch {
    static int search(int[] values, int target, int low, int high) {
        if (low > high) {
            return -1;                              // empty range
        }
        int mid = low + (high - low) / 2;
        if (values[mid] == target) {
            return mid;
        }
        if (values[mid] < target) {
            return search(values, target, mid + 1, high);
        }
        return search(values, target, low, mid - 1);
    }
 
    public static void main(String[] args) {
        int[] marks = {3, 8, 15, 21, 27, 34, 42, 56, 63, 71};
        System.out.println(search(marks, 3, 0, marks.length - 1));
        System.out.println(search(marks, 71, 0, marks.length - 1));
        System.out.println(search(marks, 99, 0, marks.length - 1));
    }
}

0
9
-1

Explanation: each call either finds the target, or calls itself with half the range. The base case low > high stops the recursion when nothing is left. The loop version is usually preferred in Java because it uses O(1) memory, while the recursive one uses O(log n) stack frames.

The JDK's Binary Search

You rarely need to write binary search yourself. The JDK has it for arrays and lists:

When the key isn't found, these methods return -(insertionPoint) - 1: a negative number that also tells you where the key would go.

import java.util.Arrays;
 
public class JdkSearch {
    public static void main(String[] args) {
        int[] marks = {3, 8, 15, 21, 27, 34, 42, 56, 63, 71};
        System.out.println(Arrays.binarySearch(marks, 56));
 
        int result = Arrays.binarySearch(marks, 20);
        int insertAt = -result - 1;
        System.out.println(result + " -> 20 would go at index " + insertAt);
    }
}

7
-4 -> 20 would go at index 3

Explanation: 56 is at index 7. 20 isn't in the array, so the method returns a negative number. Converting it with -result - 1 gives 3: the index where 20 belongs to keep the array sorted (between 15 at index 2 and 21 at index 3).

Complexity

Sorting first costs O(n log n), so binary search pays off when you search the same data many times.

Interview Corner

Practice

1. Easy: Change BinarySearch.java to count the steps and print them. Search for every value in the array and find the largest step count.
2. Harder: Write firstOccurrence(int[] values, int target) for the sorted array {2, 4, 4, 4, 7, 9}. It must return 1 for target 4.

Key Takeaways