Linear Search — String == Bug Crashes Customer Lookup

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) {\\n\\n        // Start at the very first element (index 0) and walk forward one step at a time\\n        for (int index = 0; index < numbers.length; index++) {\\n\\n            // Ask the key question: is THIS element the one we're looking for?\\n            if (numbers[index] == target) {\\n                // Yes! Stop immediately and report WHERE we found it\\n                return index;\\n            }\\n            // No match — the loop automatically moves to the next index\\n        }\\n\\n        // If we reach here, we checked every single element and found nothing\\n        // Returning -1 is the universal convention for 'not found'\\n        return -1;\\n    }\\n\\n    public static void main(String[] args) {\\n\\n        int[] studentIds = {1042, 3387, 2291, 4410, 1895};\\n        int targetId = 4410;\\n\\n        int resultIndex = linearSearch(studentIds, targetId);\\n\\n        // -1 means the target was not found anywhere in the array\\n        if (resultIndex != -1) {\\n            System.out.println(\\\"Student ID \\\" + targetId + \\\" found at index \\\" + resultIndex);\\n        } else {\\n            System.out.println(\\\"Student ID \\\" + targetId + \\\" does not exist in the list.\\\");\\n        }\\n\\n        // Now test the 'not found' case\\n        int missingId = 9999;\\n        int missingResult = linearSearch(studentIds, missingId);\\n\\n        if (missingResult != -1) {\\n            System.out.println(\\\"Student ID \\\" + missingId + \\\" found at index \\\" + missingResult);\\n        } else {\\n            System.out.println(\\\"Student ID \\\" + missingId + \\\" does not exist in the list.\\\");\\n        }\\n    }\\n}\",\n        \"output\": \"Student ID 4410 found at index 3\\nStudent ID 9999 does not exist in the list.\"\n      },\n      \"callout\": {\n        \"type\": \"info\",\n        \"title\": \"Why -1 and not 0?\",\n        \"text\": \"Returning -1 for 'not found' is a convention used across almost every language and library (Java's String.indexOf(), Python's list.find(), etc.). You can't use 0 because 0 is a valid index — it means 'found at the very first position.' Negative numbers can never be valid array indices, so -1 is a safe, unambiguous sentinel value.\"\n      },\n      \"production_insight\": \"In production, returning -1 is a contract: the caller must check it before using the index. A common failure pattern is array[-1] which throws ArrayIndexOutOfBoundsException.\\nJava's String.indexOf() returns -1, and the coding style is: if (result != -1) { use it }.\\nRule: never assume the result is valid — always guard against -1.\",\n      \"key_takeaway\": \"Return -1 for 'not found' — it's the universal sentinel that can't be confused with a valid index.\\nAlways check the return value before treating it as an array subscript.\"\n    },\n    {
      "heading": "Time and Space Complexity — What It Costs to Run Linear Search",
      "content": "Every algorithm has a cost. That cost is measured in two ways: time (how many steps does it take?) and space (how much extra memory does it need?). Understanding this for linear search is crucial — not because it's hard, but because it's the baseline you'll compare every other search algorithm against for the rest of your career.\\n\\n**Time Complexity — the 'how long' question:**\\nIn the best case, the target is the very first element. One comparison, done. That's O(1) — constant time. In the worst case, the target is the last element, or it's not in the list at all. You checked every single element — that's n comparisons for a list of n items. That's O(n) — linear time, which is where the algorithm gets its name. On average, you'll find the target somewhere in the middle, which is roughly n/2 comparisons — still O(n) because we drop constants in Big O notation.\\n\\n**Space Complexity — the 'how much memory' question:**\\nLinear search is O(1) space. It doesn't create any new arrays or data structures. It just uses a single loop variable (the index counter). No matter if your input has 10 items or 10 million, the extra memory used stays constant.\\n\\nThe honest takeaway: linear search is slow for large datasets but costs almost nothing in memory. It's the algorithm equivalent of a reliable old bicycle — not the fastest thing on the road, but it always gets you there and never breaks down.",
      "code": {
        "language": "java",
        "filename": "LinearSearchComplexityDemo.java",
        "code": "public class LinearSearchComplexityDemo {\\n\\n    // We'll count comparisons manually so you can SEE the O(n) behaviour\\n    public static int linearSearchWithCount(int[] numbers, int target) {\\n        int comparisonCount = 0; // Track how many times we check an element\\n\\n        for (int index = 0; index < numbers.length; index++) {\\n            comparisonCount++; // Every loop iteration is one comparison\\n\\n            if (numbers[index] == target) {\\n                System.out.println(\\\"Found after \\\" + comparisonCount + \\\" comparison(s).\\\");\\n                return index;\\n            }\\n        }\\n\\n        System.out.println(\\\"Not found. Made \\\" + comparisonCount + \\\" comparison(s) — checked every element.\\\");\\n        return -1;\\n    }\\n\\n    public static void main(String[] args) {\\n        int[] temperatures = {72, 68, 91, 55, 83, 77, 64, 98, 45, 88};\\n        // Array has 10 elements (indices 0 through 9)\\n\\n        System.out.println(\\\"--- Best Case: Target is the FIRST element ---\\\");\\n        linearSearchWithCount(temperatures, 72); // At index 0\\n\\n        System.out.println();\\n\\n        System.out.println(\\\"--- Average Case: Target is somewhere in the MIDDLE ---\\\");\\n        linearSearchWithCount(temperatures, 83); // At index 4\\n\\n        System.out.println();\\n\\n        System.out.println(\\\"--- Worst Case: Target is the LAST element ---\\\");\\n        linearSearchWithCount(temperatures, 88); // At index 9\\n\\n        System.out.println();\\n\\n        System.out.println(\\\"--- Worst Case: Target does NOT exist ---\\\");\\n        linearSearchWithCount(temperatures, 100); // Not in the array\\n    }\\n}\",\n        \"output\": \"--- Best Case: Target is the FIRST element ---\\nFound after 1 comparison(s).\\n\\n--- Average Case: Target is somewhere in the MIDDLE ---\\nFound after 5 comparison(s).\\n\\n--- Worst Case: Target is the LAST element ---\\nFound after 10 comparison(s).\\n\\n--- Worst Case: Target does NOT exist ---\\nNot found. Made 10 comparison(s) — checked every element.\"\n      }",
      "callout": {
        "type": "tip",
        "title": "Interview Gold: Always state all three cases",
        "text": "When an interviewer asks about complexity, don't just say 'O(n).' Say: 'Best case is O(1) if the target is the first element, worst case is O(n) if the target is last or absent, and average case is O(n). Space complexity is O(1) because no extra data structures are created.' This shows you actually understand the algorithm, not just memorised a label."
      },
      "production_insight": "In a real system, O(n) time can be hidden. For example, a cron job that searches a 50,000-row CSV every minute using linear search will consume ~50k comparisons per run.\nThat's fine alone. But if the search is inside a request-response cycle for 1000 users, that's 50 million comparisons — response times balloon.\nRule: measure the total operations per second, not just the single search cost.",
      "key_takeaway": "Best case O(1), worst O(n), space O(1).\nThe same O(n) that's fine on your laptop may be disastrous at production scale.\nAlways consider the frequency of searches, not just the size of the array."
    },
    {
      "heading": "Linear Search on Strings and Custom Objects — It's Not Just for Numbers",
      "content": "Every example you see in textbooks uses integers. That's fine for learning, but real-world code searches through names, emails, product titles, and custom objects. Linear search works on all of these — the logic is identical. The only thing that changes is how you compare two elements.\n\nWith integers, you use ==. With Strings in Java, you must use .equals() — because == on objects checks whether two variables point to the same memory address, not whether they have the same content. This is one of the most common bugs beginners write, and it's the kind of bug that can pass your own manual tests but fail in production when the string comes from user input or a database.\n\nWith custom objects (like a Student class), you decide what 'equal' means. You might search by name, by ID, or by email. You write the comparison logic yourself. This makes linear search incredibly flexible — you can search any collection for any criteria without sorting or pre-processing anything first. That flexibility is genuinely valuable in small collections and quick scripts.",
      "code": {
        "language": "java",
        "filename": "LinearSearchStringsAndObjects.java",
        "code": "public class LinearSearchStringsAndObjects {\n\n    // --- Searching through an array of Strings ---\n    public static int searchByName(String[] names, String targetName) {\\n        for (int index = 0; index < names.length; index++) {\\n            // CRITICAL: Use .equals() for Strings, NOT ==\\n            // .equals() compares the actual text content character by character\\n            if (names[index].equals(targetName)) {\\n                return index;\\n            }
        }
        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) {\\n            this.studentId = studentId;\\n            this.fullName = fullName;\\n            this.gpa = gpa;\\n        }
    }

    // --- Searching through an array of Student objects by their ID ---
    public static Student searchById(Student[] roster, int targetId) {\\n        for (int index = 0; index < roster.length; index++) {\\n            // We define what 'match' means: two students match if their IDs are equal\\n            if (roster[index].studentId == targetId) {\\n                return roster[index]; // Return the whole Student object, not just the index\\n            }
        }
        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 {\\n        String name;\\n        double priceInDollars;\\n        boolean inStock;\\n\\n        Product(String name, double priceInDollars, boolean inStock) {\\n            this.name = name;\\n            this.priceInDollars = priceInDollars;\\n            this.inStock = inStock;\\n        }
    }

    // Returns ALL in-stock products at or below the budget — not just the first one
    public static List<Product> findAffordableInStockProducts(
            Product[] catalogue, double budget) {\\n\\n        List<Product> matches = new ArrayList<>();\\n\\n        for (int index = 0; index < catalogue.length; index++) {\\n            // Two conditions must BOTH be true to add this product to results\\n            boolean withinBudget = catalogue[index].priceInDollars <= budget;\\n            boolean available = catalogue[index].inStock;\\n\\n            if (withinBudget && available) {\\n                matches.add(catalogue[index]); // Collect the match; keep going\\n            }
            // 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 + ")");
        }
    }
}

def linear_search(arr, target):
    """
    Return the index of target in arr, or -1 if not found.
    Works on lists, tuples, or any sequence supporting indexing.
    """
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# Example usage
student_ids = [1042, 3387, 2291, 4410, 1895]
result = linear_search(student_ids, 4410)
print(f"Found at index: {result}" if result != -1 else "Not found")

# Testing with strings
names = ["Alice", "Bob", "Charlie"]
print(linear_search(names, "Bob"))   # Output: 1
print(linear_search(names, "Dave"))  # Output: -1

// io.thecodeforge — dsa tutorial

public class SentinelUserLookup {

    // Returns index of target, or -1. Does NOT modify original array.
    public static int findIndex(int[] activeSessions, int targetUserId) {
        if (activeSessions == null || activeSessions.length == 0) {
            return -1;
        }

        // Save last element and replace with sentinel
        int last = activeSessions[activeSessions.length - 1];
        activeSessions[activeSessions.length - 1] = targetUserId;

        int idx = 0;
        // Only one comparison per iteration — no bounds check
        while (activeSessions[idx] != targetUserId) {
            idx++;
        }

        // Restore original last element (critical in prod!)
        activeSessions[activeSessions.length - 1] = last;

        // If we found it at the original last slot, it might be sentinel
        if (idx < activeSessions.length - 1 || last == targetUserId) {
            return idx;
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] sessionIds = {1001, 2003, 4012, 5123, 6789};
        int target = 4012;
        int result = findIndex(sessionIds, target);
        System.out.println("Session " + target + " found at: " + result);
        System.out.println("Original array intact: " + java.util.Arrays.toString(sessionIds));
    }
}

// io.thecodeforge — dsa tutorial

public class MoveToFrontSearch {

    // Returns index of target and moves it one step toward index 0
    public static int searchAndPromote(int[] recentOrders, int targetOrderId) {
        for (int idx = 0; idx < recentOrders.length; idx++) {
            if (recentOrders[idx] == targetOrderId) {
                // Swap with the element just before, if not already at head
                if (idx > 0) {
                    int predecessor = recentOrders[idx - 1];
                    recentOrders[idx - 1] = recentOrders[idx];
                    recentOrders[idx] = predecessor;
                    // Return the new (swapped) position
                    return idx - 1;
                }
                return idx; // Already at front
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        int[] orderIds = {5001, 3002, 7003, 1004, 9005};
        System.out.println("Initial: " + java.util.Arrays.toString(orderIds));

        // Simulate repeated lookups of the same hot item
        searchAndPromote(orderIds, 7003);
        System.out.println("After 1st lookup of 7003: " + java.util.Arrays.toString(orderIds));
        searchAndPromote(orderIds, 7003);
        System.out.println("After 2nd lookup of 7003: " + java.util.Arrays.toString(orderIds));
        searchAndPromote(orderIds, 7003);
        System.out.println("After 3rd lookup of 7003: " + java.util.Arrays.toString(orderIds));
    }
}

// io.thecodeforge — dsa tutorial
// Pseudocode for Linear Search
// 1. function linearSearch(arr, target)
// 2.   for i from 0 to arr.length - 1
// 3.     if arr[i] == target
// 4.       return i
// 5.   return -1
// 6. end function

public class LinearSearchPseudocode {
    public static int linearSearch(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) return i;
        }
        return -1;
    }
}

// io.thecodeforge — dsa tutorial
// Analysis: Worst-case O(n), Best-case O(1)
public class LinearSearchAnalysis {
    public static int search(int[] arr, int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) return i; // branch
        }
        return -1; // worst case: n comparisons
    }
}