Binary Search

// Binary search over a sorted array (Zerethon Official Sample: binary-search 1.5.0).
import java.util.ArrayList;
import java.util.List;

public class BinarySearch {
    /** Return the index of target in a (sorted ascending), or -1 if it is absent. */
    public static int binarySearch(int[] a, int target) {
        int lo = 0;
        int hi = a.length - 1;
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            if (a[mid] == target) return mid;
            if (a[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return -1;
    }

    /** Every comparison binarySearch makes, as {lo, mid, hi}. */
    public static List<int[]> binarySearchSteps(int[] a, int target) {
        List<int[]> steps = new ArrayList<>();
        int lo = 0;
        int hi = a.length - 1;
        while (lo <= hi) {
            int mid = (lo + hi) >>> 1;
            steps.add(new int[] {lo, mid, hi});
            if (a[mid] == target) break;
            if (a[mid] < target) lo = mid + 1;
            else hi = mid - 1;
        }
        return steps;
    }
}

// Checks for binarySearch. To run them, set this file as the entry file
// (the ▶ button next to it in Files) and press Run.
public class BinarySearchTest {
    public static void main(String[] args) {
        int[] range = new int[500];
        for (int i = 0; i < range.length; i++) range[i] = i * 2;
        Object[][] cases = {
            {new int[] {}, 1, -1},
            {new int[] {4}, 4, 0},
            {new int[] {4}, 5, -1},
            {new int[] {1, 3, 5, 7, 9}, 1, 0},
            {new int[] {1, 3, 5, 7, 9}, 9, 4},
            {new int[] {1, 3, 5, 7, 9}, 6, -1},
            {range, 998, 499},
        };

        for (Object[] c : cases) {
            int[] a = (int[]) c[0];
            int target = (int) c[1];
            int expected = (int) c[2];
            int actual = BinarySearch.binarySearch(a, target);
            if (actual != expected) {
                System.err.printf("binarySearch(length %d, %d): expected %d, got %d%n", a.length, target, expected, actual);
                System.exit(1);
            }
        }

        System.out.println("All " + cases.length + " checks passed.");
    }
}

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int[] numbers = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        System.out.println("Sorted list: " + Arrays.toString(numbers));
        System.out.println();

        for (int target : new int[] {23, 2, 91, 7}) {
            int index = BinarySearch.binarySearch(numbers, target);
            String result = index != -1 ? "found at index " + index : "not found";
            System.out.printf("search %2d: %s%n", target, result);
        }

        System.out.println();
        System.out.println("Steps for 23 (lo, mid, hi):");
        for (int[] step : BinarySearch.binarySearchSteps(numbers, 23)) {
            System.out.printf("  lo=%d mid=%d hi=%d -> a[mid]=%d%n", step[0], step[1], step[2], numbers[step[1]]);
        }
    }
}

# Binary Search

Zerethon Official Sample `binary-search`, version 1.5.0, Java 25.

- `BinarySearch.java` — the algorithm (`binarySearch`, and `binarySearchSteps` to trace it)
- `Main.java` — entry file: searches a few values and prints the steps
- `BinarySearchTest.java` — checks; set it as the entry file to run them

Every `.java` file is compiled together before the entry file's class runs. In Java the file
`Name.java` holds `public class Name`.

This project is your own copy. Changing it never changes the official sample.
See the algorithm animated: https://tools.zerethon.com/binary-search-visualizer