Linear Search Algorithm Explained — How It Works, When to Use It, and Why It Matters

public class LinearSearchBasic {

    /**
     * Searches for a target value inside an array of integers.
     *
     * @param numbers  The array we want to search through
     * @param target   The number we're looking for
     * @return         The index where the target was found, or -1 if it doesn't exist
     */
    public static int linearSearch(int[] numbers, int target) {

        // Start at the very first element (index 0) and walk forward one step at a time
        for (int index = 0; index < numbers.length; index++) {

            // Ask the key question: is THIS element the one we're looking for?
            if (numbers[index] == target) {
                // Yes! Stop immediately and report WHERE we found it
                return index;
            }
            // No match — the loop automatically moves to the next index
        }

        // If we reach here, we checked every single element and found nothing
        // Returning -1 is the universal convention for 'not found'
        return -1;
    }

    public static void main(String[] args) {

        int[] studentIds = {1042, 3387, 2291, 4410, 1895};
        int targetId = 4410;

        int resultIndex = linearSearch(studentIds, targetId);

        // -1 means the target was not found anywhere in the array
        if (resultIndex != -1) {
            System.out.println("Student ID " + targetId + " found at index " + resultIndex);
        } else {
            System.out.println("Student ID " + targetId + " does not exist in the list.");
        }

        // Now test the 'not found' case
        int missingId = 9999;
        int missingResult = linearSearch(studentIds, missingId);

        if (missingResult != -1) {
            System.out.println("Student ID " + missingId + " found at index " + missingResult);
        } else {
            System.out.println("Student ID " + missingId + " does not exist in the list.");
        }
    }
}

public class LinearSearchComplexityDemo {

    // We'll count comparisons manually so you can SEE the O(n) behaviour
    public static int linearSearchWithCount(int[] numbers, int target) {
        int comparisonCount = 0; // Track how many times we check an element

        for (int index = 0; index < numbers.length; index++) {
            comparisonCount++; // Every loop iteration is one comparison

            if (numbers[index] == target) {
                System.out.println("Found after " + comparisonCount + " comparison(s).");
                return index;
            }
        }

        System.out.println("Not found. Made " + comparisonCount + " comparison(s) — checked every element.");
        return -1;
    }

    public static void main(String[] args) {
        int[] temperatures = {72, 68, 91, 55, 83, 77, 64, 98, 45, 88};
        // Array has 10 elements (indices 0 through 9)

        System.out.println("--- Best Case: Target is the FIRST element ---");
        linearSearchWithCount(temperatures, 72); // At index 0

        System.out.println();

        System.out.println("--- Average Case: Target is somewhere in the MIDDLE ---");
        linearSearchWithCount(temperatures, 83); // At index 4

        System.out.println();

        System.out.println("--- Worst Case: Target is the LAST element ---");
        linearSearchWithCount(temperatures, 88); // At index 9

        System.out.println();

        System.out.println("--- Worst Case: Target does NOT exist ---");
        linearSearchWithCount(temperatures, 100); // Not in the array
    }
}

public class LinearSearchStringsAndObjects {

    // --- Searching through an array of Strings ---
    public static int searchByName(String[] names, String targetName) {
        for (int index = 0; index < names.length; index++) {
            // CRITICAL: Use .equals() for Strings, NOT ==
            // .equals() compares the actual text content character by character
            if (names[index].equals(targetName)) {
                return index;
            }
        }
        return -1; // Name not found
    }

    // --- A simple Student record to demonstrate searching objects ---
    static class Student {
        int studentId;
        String fullName;
        double gpa;

        Student(int studentId, String fullName, double gpa) {
            this.studentId = studentId;
            this.fullName = fullName;
            this.gpa = gpa;
        }
    }

    // --- Searching through an array of Student objects by their ID ---
    public static Student searchById(Student[] roster, int targetId) {
        for (int index = 0; index < roster.length; index++) {
            // We define what 'match' means: two students match if their IDs are equal
            if (roster[index].studentId == targetId) {
                return roster[index]; // Return the whole Student object, not just the index
            }
        }
        return null; // Convention: return null when a searched object isn't found
    }

    public static void main(String[] args) {

        // --- String search demo ---
        String[] cityNames = {"Austin", "Denver", "Phoenix", "Nashville", "Portland"};
        String searchCity = "Nashville";

        int cityIndex = searchByName(cityNames, searchCity);
        if (cityIndex != -1) {
            System.out.println(searchCity + " found at index " + cityIndex);
        } else {
            System.out.println(searchCity + " is not in the list.");
        }

        // --- Object search demo ---
        Student[] classRoster = {
            new Student(1001, "Maria Chen", 3.8),
            new Student(1042, "James Okafor", 3.5),
            new Student(1087, "Priya Nair", 3.9),
            new Student(1103, "Lucas Ferreira", 3.2)
        };

        int searchId = 1087;
        Student foundStudent = searchById(classRoster, searchId);

        if (foundStudent != null) {
            System.out.println("Found student: " + foundStudent.fullName
                + " | GPA: " + foundStudent.gpa);
        } else {
            System.out.println("No student with ID " + searchId + " found.");
        }
    }
}

import java.util.ArrayList;
import java.util.List;

public class LinearSearchRealWorldUse {

    // Real-world use case: find all products under a given price threshold
    // This CAN'T use binary search because we want ALL matches, not just one,
    // and the condition is a range, not an exact value.
    // Linear search is genuinely the right tool here.

    static class Product {
        String name;
        double priceInDollars;
        boolean inStock;

        Product(String name, double priceInDollars, boolean inStock) {
            this.name = name;
            this.priceInDollars = priceInDollars;
            this.inStock = inStock;
        }
    }

    // Returns ALL in-stock products at or below the budget — not just the first one
    public static List<Product> findAffordableInStockProducts(
            Product[] catalogue, double budget) {

        List<Product> matches = new ArrayList<>();

        for (int index = 0; index < catalogue.length; index++) {
            // Two conditions must BOTH be true to add this product to results
            boolean withinBudget = catalogue[index].priceInDollars <= budget;
            boolean available = catalogue[index].inStock;

            if (withinBudget && available) {
                matches.add(catalogue[index]); // Collect the match; keep going
            }
            // Notice: we do NOT return early — we need to check every product
        }

        return matches; // Return everything we found
    }

    public static void main(String[] args) {
        Product[] storeCatalogue = {
            new Product("Wireless Earbuds",  79.99,  true),
            new Product("Laptop Stand",       45.00,  true),
            new Product("Mechanical Keyboard", 129.99, false), // Out of stock
            new Product("USB Hub",             35.50,  true),
            new Product("Webcam HD",           89.99,  true),
            new Product("Monitor Light",       49.99,  false) // Out of stock
        };

        double userBudget = 80.00;

        List<Product> recommendations =
            findAffordableInStockProducts(storeCatalogue, userBudget);

        System.out.println("In-stock products under $" + userBudget + ":");
        for (Product product : recommendations) {
            System.out.println("  - " + product.name
                + " ($" + product.priceInDollars + ")");
        }
    }
}