Binary Search in Java

intermediate· Arrays · Searching

Problem

Binary search finds a target in a sorted array by repeatedly checking the middle element and discarding the half of the array that can't contain the target.

Given a sorted array of integers and a target value, find the index of the target, or report that it isn't present.

Input

[2, 5, 9, 14, 20, 27, 31], target = 20

Output

Element found at index: 4

Java Program

Java

public class BinarySearch {
    public static void main(String[] args) {
        int[] arr = {2, 5, 9, 14, 20, 27, 31};
        int target = 20;
        int low = 0, high = arr.length - 1;
        int index = -1;

        while (low <= high) {
            int mid = low + (high - low) / 2; // avoids the overflow (low + high) / 2 could risk on large indices
            if (arr[mid] == target) {
                index = mid; // found it
                break;
            } else if (arr[mid] < target) {
                low = mid + 1; // target must be in the right half
            } else {
                high = mid - 1; // target must be in the left half
            }
        }

        System.out.println("Element found at index: " + index);
    }
}

▶ Run Code

Output

Element found at index: 4

Core Logic

Checking the middle element and discarding the half of the array that can't hold the target, then repeating on the remaining half, narrows the search range exponentially fast.

How It Works

1low and high start at the first and last valid indices, marking the current search range.
2While low <= high, mid is calculated as the midpoint of the current range.
3If arr[mid] equals the target, its index is the answer, found immediately.
4If arr[mid] is less than the target, the target must be in the right half, so low moves past mid; if it's greater, the target must be in the left half, so high moves before mid.

For [2, 5, 9, 14, 20, 27, 31] searching for 20, the first mid is index 3 (14) — too small, so the search continues in the right half and lands on index 4 (20).

💡

Key Point: This only works because the array is sorted — on an unsorted array, discarding half the elements based on one comparison would risk throwing away the target itself.

Complexity

Time Complexity: O(log n)Space Complexity: O(1)

Why: Each comparison discards half of the remaining search range, so the range shrinks to nothing after about log₂n steps, using only the low/high/mid variables.

Key Concepts

low/high/mid pointerswhile loopsearch range halving

Approach 2: Using Arrays.binarySearch()

Java

import java.util.Arrays;

public class BinarySearchBuiltin {
    public static void main(String[] args) {
        int[] arr = {2, 5, 9, 14, 20, 27, 31};
        int target = 20;
        // binarySearch() requires the array to already be sorted
        int index = Arrays.binarySearch(arr, target);
        System.out.println("Element found at index: " + index);
    }
}

▶ Run Code

Output

Element found at index: 4

Core Logic

In real code, there's no reason to write the low/high/mid loop yourself — Arrays.binarySearch() already implements binary search on a sorted array in one call.

How It Works

1Arrays.binarySearch(arr, target) takes the sorted array and the value to find.
2It returns the index of the target if found, using the same halving strategy as the manual version internally.
3If the target isn't present, it returns a negative number instead — not simply -1.

Arrays.binarySearch(new int[]{2, 5, 9, 14, 20, 27, 31}, 20) returns 4 in a single call.

💡

Key Point: The array MUST already be sorted before calling this — Arrays.binarySearch() doesn't check, and will silently return an unreliable result on unsorted input.

Complexity

Time Complexity: O(log n)Space Complexity: O(1)

Why: Arrays.binarySearch() still halves the search range on every comparison internally, the same underlying algorithm as the manual loop.

Key Concepts

Arrays.binarySearch()

← Previous

Average Array Elements

Bubble Sort

Related Programs

Arraysbeginner

Average Array Elements

Arraysintermediate

Bubble Sort

Arraysbeginner

Check Array Is Sorted