ArraySearchDemo.java

import java.util.Arrays;
import java.util.Random;
import java.util.stream.IntStream;

/**
 * Four array searching algorithms, from the simplest to the most efficient,
 * each illustrating a different optimization idea.
 * <p>
 * <ol>
 *   <li><b>Linear search</b> — the baseline. Checks every element left to
 *       right. O(n) with two comparisons per element (bounds + value).</li>
 *   <li><b>Sentinel search</b> — a clever trick that temporarily plants the
 *       target at the end of the array, eliminating the bounds check from
 *       the inner loop. Still O(n), but roughly half the comparisons.</li>
 *   <li><b>Unrolled search</b> — processes two elements per iteration,
 *       halving the number of loop-control bounds checks. A technique
 *       borrowed from high-performance computing (Duff's device, etc.).</li>
 *   <li><b>Binary search</b> — for <em>sorted</em> arrays only. Halves the
 *       search space each step, giving O(log n) performance.</li>
 * </ol>
 * <p>
 * All methods are static (they don't need instance state) and the main method
 * benchmarks them side by side.
 *
 * @author Ilkka Kokkarinen
 */
public class ArraySearchDemo {

    // -----------------------------------------------------------------------
    // 1. Linear search — the straightforward baseline.
    //
    // Two comparisons per element: one for bounds, one for value.
    // -----------------------------------------------------------------------

    /**
     * Search for {@code target} in {@code array} by scanning left to right.
     *
     * @param array  the array to search
     * @param target the value to find
     * @return the index of the first occurrence, or -1 if not found
     */
    public static int linearSearch(int[] array, int target) {
        int i = 0;
        while (i < array.length && array[i] != target) { i++; }
        return (i < array.length) ? i : -1;
    }

    // -----------------------------------------------------------------------
    // 2. Sentinel search — eliminate the bounds check.
    //
    // By temporarily placing the target at the last position, the loop is
    // guaranteed to terminate without ever checking i < array.length.
    // After the loop, we restore the original last element and figure out
    // whether we found a real match or just hit the sentinel.
    //
    // IMPORTANT: this mutates the array temporarily, so it is NOT safe for
    // concurrent use. It also requires a non-empty array.
    // -----------------------------------------------------------------------

    /**
     * Search for {@code target} using a sentinel at the end of the array.
     * The inner loop contains only a single comparison per element.
     *
     * @param array  the array to search (must be non-empty; temporarily mutated)
     * @param target the value to find
     * @return the index of the first occurrence, or -1 if not found
     */
    public static int sentinelSearch(int[] array, int target) {
        int lastIndex = array.length - 1;
        int savedLast = array[lastIndex];  // Save the last element.
        array[lastIndex] = target;         // Plant the sentinel.

        int i = 0;
        while (array[i] != target) { i++; } // No bounds check needed!

        array[lastIndex] = savedLast;      // Restore the original value.

        // Did we find a real match, or just the sentinel?
        return (i < lastIndex || savedLast == target) ? i : -1;
    }

    // -----------------------------------------------------------------------
    // 3. Unrolled search — process two elements per iteration.
    //
    // Each iteration checks two consecutive elements against the target,
    // cutting the number of loop-control (bounds) checks in half. If the
    // array has an odd number of elements, we handle the first one separately
    // so the main loop always processes pairs.
    //
    // This is a simplified version of "loop unrolling", a technique from
    // high-performance computing. The classic extreme version is Duff's
    // Device, which is worth looking up for entertainment value alone.
    // -----------------------------------------------------------------------

    /**
     * Search for {@code target} with a loop unrolled to two elements per step.
     *
     * @param array  the array to search
     * @param target the value to find
     * @return the index of the first occurrence, or -1 if not found
     */
    public static int unrolledSearch(int[] array, int target) {
        int i = 0;
        // Handle the odd element so the main loop always has pairs.
        if (array.length % 2 == 1) {
            if (array[i++] == target) { return 0; }
        }
        // Main loop: two elements per iteration, one bounds check.
        while (i < array.length) {
            if (array[i++] == target) { return i - 1; }
            if (array[i++] == target) { return i - 1; }
        }
        return -1;
    }

    // -----------------------------------------------------------------------
    // 4. Binary search — O(log n) for sorted arrays.
    //
    // Maintains a range [low, high] that is guaranteed to contain the target
    // if it exists. Each step picks the midpoint and discards half the range.
    //
    // If the target is not found, returns the insertion point — the index
    // where the target would need to be inserted to keep the array sorted.
    // This makes binary search useful for more than just "is it there?".
    // -----------------------------------------------------------------------

    /**
     * Search for {@code target} in a sorted array using binary search.
     * <p>
     * If found, returns the index of the target. If not found, returns the
     * <em>insertion point</em>: the index where the target would go to keep
     * the array in sorted order. Returns {@code array.length} if the target
     * is larger than every element.
     *
     * @param sorted the array to search (must be sorted in ascending order)
     * @param target the value to find
     * @return the index of the target or its insertion point
     */
    public static int binarySearch(int[] sorted, int target) {
        int low = 0;
        int high = sorted.length - 1;

        if (sorted[high] < target) { return sorted.length; } // Larger than all elements.

        while (low < high) {
            int mid = low + (high - low) / 2; // Overflow-safe midpoint.
            if (sorted[mid] < target) {
                low = mid + 1;  // Target must be to the right.
            } else {
                high = mid;     // Target is here or to the left.
            }
        }
        return low;
    }

    // -----------------------------------------------------------------------
    // Benchmarking helper.
    // -----------------------------------------------------------------------

    @FunctionalInterface
    private interface SearchMethod {
        int search(int[] array, int target);
    }

    /**
     * Time a search method over many random lookups and return the average
     * nanoseconds per search.
     */
    private static double benchmarkSearch(String name, SearchMethod method,
                                          int[] array, int[] targets) {
        // Warmup run (JIT compilation).
        for (int target : targets) { method.search(array, target); }

        long start = System.nanoTime();
        int dummy = 0; // Prevent dead-code elimination.
        for (int target : targets) {
            dummy += method.search(array, target);
        }
        long elapsed = System.nanoTime() - start;
        double nanosPerSearch = (double) elapsed / targets.length;
        System.out.printf("  %-18s %8.1f ns/search%n", name, nanosPerSearch);
        return nanosPerSearch + dummy * 0.0; // Use dummy to prevent optimization.
    }

    // -----------------------------------------------------------------------
    // Main — verify correctness and benchmark all four algorithms.
    // -----------------------------------------------------------------------

    public static void main(String[] args) {
        var rng = new Random(42);

        // --- Correctness verification ---
        System.out.println("=== Correctness Verification ===\n");
        int[] testArray = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
        System.out.println("Array: " + Arrays.toString(testArray));
        System.out.println();

        for (int target : new int[]{5, 9, 7, 3}) {
            System.out.printf("Searching for %d:%n", target);
            System.out.printf("  linearSearch:   %d%n", linearSearch(testArray, target));
            System.out.printf("  sentinelSearch: %d%n", sentinelSearch(testArray, target));
            System.out.printf("  unrolledSearch: %d%n", unrolledSearch(testArray, target));
            System.out.println();
        }

        // Binary search on a sorted array.
        int[] sortedArray = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
        System.out.println("Sorted array: " + Arrays.toString(sortedArray));
        for (int target : new int[]{23, 1, 50, 100}) {
            int result = binarySearch(sortedArray, target);
            boolean found = (result < sortedArray.length && sortedArray[result] == target);
            System.out.printf("  binarySearch(%d): index=%d (%s)%n",
                    target, result, found ? "found" : "insertion point");
        }

        // --- Benchmark ---
        System.out.println("\n=== Benchmark (unsorted, n=100,000) ===\n");
        int size = 100_000;
        int[] largeArray = rng.ints(size, 0, size * 10).toArray();
        int[] targets = rng.ints(10_000, 0, size * 10).toArray();

        benchmarkSearch("linearSearch",   ArraySearchDemo::linearSearch,   largeArray, targets);
        benchmarkSearch("sentinelSearch", ArraySearchDemo::sentinelSearch, largeArray, targets);
        benchmarkSearch("unrolledSearch", ArraySearchDemo::unrolledSearch, largeArray, targets);

        // Binary search needs a sorted copy.
        int[] sortedLarge = largeArray.clone();
        Arrays.sort(sortedLarge);
        System.out.println();
        System.out.println("  (Binary search on sorted copy:)");
        benchmarkSearch("binarySearch",   ArraySearchDemo::binarySearch,   sortedLarge, targets);

        // --- Verify all linear searches agree ---
        System.out.println("\n=== Agreement Check ===\n");
        boolean allAgree = IntStream.of(targets).allMatch(t -> {
            int r1 = linearSearch(largeArray, t);
            int r2 = sentinelSearch(largeArray, t);
            int r3 = unrolledSearch(largeArray, t);
            return r1 == r2 && r2 == r3;
        });
        System.out.println("All three linear searches agree on every target: " + allAgree);
    }
}