Array Searching in Java: Linear vs Binary Search Explained

public class LinearSearchDemo {

    /**
     * Searches for a target score in an array of exam scores.
     * Returns the index of the target if found, or -1 if not found.
     *
     * @param scores  the array to search through
     * @param target  the score we are looking for
     * @return        the index of the target, or -1
     */
    public static int linearSearch(int[] scores, int target) {
        // Loop through every position in the array, one by one
        for (int index = 0; index < scores.length; index++) {

            // Check if the current element matches our target
            if (scores[index] == target) {
                return index; // Found it! Return its position immediately
            }
        }

        // We checked every element and never found the target
        return -1;
    }

    public static void main(String[] args) {
        // A small class of students' exam scores — NOT sorted on purpose
        int[] examScores = {72, 85, 91, 60, 78, 95, 88, 67};

        int targetScore = 95;
        int notPresentScore = 50;

        // --- Search 1: Looking for a score that EXISTS in the array ---
        int foundIndex = linearSearch(examScores, targetScore);

        if (foundIndex != -1) {
            // foundIndex holds the real position (0-based)
            System.out.println("Score " + targetScore + " found at index " + foundIndex);
        } else {
            System.out.println("Score " + targetScore + " was not found.");
        }

        // --- Search 2: Looking for a score that does NOT exist ---
        int missingIndex = linearSearch(examScores, notPresentScore);

        if (missingIndex != -1) {
            System.out.println("Score " + notPresentScore + " found at index " + missingIndex);
        } else {
            // -1 is our signal that the target was never found
            System.out.println("Score " + notPresentScore + " was not found in the array.");
        }

        // --- Show how many comparisons worst-case would require ---
        System.out.println("\nArray has " + examScores.length + " elements.");
        System.out.println("Worst case: " + examScores.length + " comparisons (linear search).");
    }
}

import java.util.Arrays; // Needed for Arrays.sort() and Arrays.binarySearch()

public class BinarySearchDemo {

    /**
     * Manual binary search implementation so you can see exactly what happens.
     * IMPORTANT: the array passed in MUST already be sorted ascending.
     *
     * @param sortedPrices  a sorted array of product prices
     * @param targetPrice   the price we are searching for
     * @return              the index of the target, or -1 if not found
     */
    public static int manualBinarySearch(int[] sortedPrices, int targetPrice) {
        int leftBoundary  = 0;                        // Start of the search zone
        int rightBoundary = sortedPrices.length - 1; // End of the search zone

        while (leftBoundary <= rightBoundary) {
            // Calculate the midpoint — avoid integer overflow with this formula
            int midpoint = leftBoundary + (rightBoundary - leftBoundary) / 2;

            System.out.println("  Checking index " + midpoint
                    + " (value: " + sortedPrices[midpoint] + ")");

            if (sortedPrices[midpoint] == targetPrice) {
                return midpoint; // Exact match — return position

            } else if (sortedPrices[midpoint] < targetPrice) {
                // The target is in the RIGHT half — discard everything left of midpoint
                leftBoundary = midpoint + 1;

            } else {
                // The target is in the LEFT half — discard everything right of midpoint
                rightBoundary = midpoint - 1;
            }
        }

        return -1; // Target not found
    }

    public static void main(String[] args) {
        // Product prices — we sort them FIRST so binary search can work
        int[] productPrices = {499, 120, 850, 35, 670, 250, 15, 980};

        System.out.println("=== Manual Binary Search ===\n");

        // Step 1: Sort the array — binary search REQUIRES this
        Arrays.sort(productPrices);
        System.out.println("Sorted prices: " + Arrays.toString(productPrices));

        // Step 2: Search for a price that exists
        int targetPrice = 250;
        System.out.println("\nSearching for price: " + targetPrice);
        int manualResult = manualBinarySearch(productPrices, targetPrice);

        if (manualResult != -1) {
            System.out.println("Found at index: " + manualResult);
        } else {
            System.out.println("Price not found.");
        }

        // Step 3: Search for a price that does NOT exist
        int missingPrice = 300;
        System.out.println("\nSearching for price: " + missingPrice);
        int missingResult = manualBinarySearch(productPrices, missingPrice);
        System.out.println(missingResult != -1
                ? "Found at index: " + missingResult
                : "Price not found.");

        // ---------------------------------------------------------------
        System.out.println("\n=== Java Built-in Arrays.binarySearch() ===\n");

        // Arrays.binarySearch() does the same job — use this in real code
        // The array must STILL be sorted before calling it
        int builtInResult = Arrays.binarySearch(productPrices, targetPrice);

        if (builtInResult >= 0) {
            // A positive (or zero) result means it was found
            System.out.println("Arrays.binarySearch() found " + targetPrice
                    + " at index: " + builtInResult);
        } else {
            // A negative result means it was NOT found
            System.out.println("Arrays.binarySearch() did not find " + targetPrice);
        }

        // Check for a missing value with the built-in method
        int builtInMissing = Arrays.binarySearch(productPrices, missingPrice);
        System.out.println("Result for missing price " + missingPrice
                + ": " + builtInMissing + " (negative = not found)");
    }
}

import java.util.Arrays;

public class StringArraySearchDemo {

    /**
     * Linear search for a username — works on unsorted arrays.
     * Uses .equalsIgnoreCase() so 'Alice' and 'alice' both match.
     */
    public static int findUsername(String[] usernames, String targetUsername) {
        for (int index = 0; index < usernames.length; index++) {
            // .equalsIgnoreCase() compares content, not memory address
            if (usernames[index].equalsIgnoreCase(targetUsername)) {
                return index;
            }
        }
        return -1;
    }

    public static void main(String[] args) {

        // --- Scenario 1: Unsorted list — use linear search ---
        String[] activeUsers = {"priya", "marco", "alice", "leon", "yuki"};

        System.out.println("=== Linear Search on Unsorted String Array ===\n");

        String searchName = "Alice"; // Different capitalisation — test .equalsIgnoreCase()
        int linearResult = findUsername(activeUsers, searchName);

        if (linearResult != -1) {
            System.out.println("'" + searchName + "' found at index " + linearResult
                    + " (stored as '" + activeUsers[linearResult] + "')");
        } else {
            System.out.println("'" + searchName + "' not found.");
        }

        // Demonstrate the == trap so you can see exactly why it fails
        System.out.println("\n--- The String == Trap (DO NOT DO THIS) ---");
        String builtFromChars = new String("priya"); // Deliberately a new object
        System.out.println("Using == :      " + (activeUsers[0] == builtFromChars));       // false — wrong!
        System.out.println("Using .equals(): " + activeUsers[0].equals(builtFromChars)); // true  — correct

        // --- Scenario 2: Sorted list — use Arrays.binarySearch() ---
        System.out.println("\n=== Binary Search on Sorted String Array ===\n");

        String[] sortedUsernames = {"alice", "leon", "marco", "priya", "yuki"};
        System.out.println("Sorted usernames: " + Arrays.toString(sortedUsernames));

        String loginAttempt = "marco";
        // Arrays.binarySearch() on Strings is case-sensitive
        int binaryResult = Arrays.binarySearch(sortedUsernames, loginAttempt);

        if (binaryResult >= 0) {
            System.out.println("Login approved: '" + loginAttempt
                    + "' found at index " + binaryResult);
        } else {
            System.out.println("Login denied: '" + loginAttempt + "' not found.");
        }

        // What happens if we search with wrong capitalisation?
        String wrongCase = "Marco"; // Capital M
        int wrongCaseResult = Arrays.binarySearch(sortedUsernames, wrongCase);
        System.out.println("\nSearching for '" + wrongCase + "' (capital M): result = "
                + wrongCaseResult + " — negative means not found!");
        System.out.println("Tip: Normalise to lowercase before sorting AND before searching.");
    }
}