Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Linear Search for Object Search

Problem Statement

Write a Java program that extends the Linear Search algorithm to find a Student object in an array of Student objects based on a given id field. The program should count the number of comparisons made during the search and test with a sample dataset containing Student objects with varied IDs, including cases where the target ID is present, absent, or duplicated. Linear Search will sequentially check each object’s id until a match is found or the array is fully traversed. You can visualize this as searching through a list of student records one by one to find a specific student by their ID number.

Input:

  • An array of Student objects, each with a name (String) and id (integer) field, and a target id to find. Output: The index of the first Student with the matching id (or -1 if not found), the number of comparisons made, and a string representation of the input array for verification. Constraints:
  • The array length n is between 0 and 10^5.
  • IDs are integers in the range [1, 10^6]. Example:
  • Input: array = [Student("Alice", 101), Student("Bob", 102), Student("Charlie", 101)], target = 101
  • Output:
    • Input Array: [Student(name=Alice, id=101), Student(name=Bob, id=102), Student(name=Charlie, id=101)]
    • Target ID: 101
    • Index: 0
    • Comparisons: 1
  • Explanation: Linear Search finds the first Student with id=101 at index 0 after 1 comparison.
  • Input: array = [Student("Alice", 101), Student("Bob", 102)], target = 103
  • Output:
    • Input Array: [Student(name=Alice, id=101), Student(name=Bob, id=102)]
    • Target ID: 103
    • Index: -1
    • Comparisons: 2
  • Explanation: Linear Search checks all elements, returns -1 as id=103 is not found.

Pseudocode

FUNCTION linearSearchObject(arr, targetId)
    SET comparisons to 0
    FOR i from 0 to length of arr - 1
        INCREMENT comparisons
        IF arr[i].id equals targetId THEN
            RETURN i, comparisons
        ENDIF
    ENDFOR
    RETURN -1, comparisons
ENDFUNCTION

FUNCTION toString(arr)
    CREATE result as new StringBuilder
    APPEND "[" to result
    FOR each element in arr
        APPEND element.toString() to result
        IF element is not last THEN
            APPEND ", " to result
        ENDIF
    ENDFOR
    APPEND "]" to result
    RETURN result as string
ENDFUNCTION

FUNCTION main()
    SET testCases to array of (Student array, targetId) pairs
    FOR each testCase in testCases
        PRINT test case details
        SET arr to testCase Student array
        SET targetId to testCase target
        CALL linearSearchObject(arr, targetId) to get index, comparisons
        PRINT input array, targetId, index, comparisons
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define Student class: a. Fields: name (String), id (integer). b. Include toString for readable output.
  2. Define linearSearchObject: a. Initialize a comparisons counter to 0. b. Iterate through the array, incrementing comparisons for each object. c. Check if the object’s id matches targetId. d. If found, return index and comparisons; else return -1 and comparisons.
  3. Define toString: a. Convert array to a string, e.g., "[Student(name=Alice, id=101), ...]".
  4. In main, test with: a. Mixed IDs (n=5, with duplicates). b. Empty array (n=0). c. Single-element array (n=1). d. Absent ID (n=6). e. Duplicate IDs (n=4, all same ID).

Java Implementation

import java.util.*;

public class LinearSearchObjectSearch {
    // Student class
    static class Student {
        String name;
        int id;

        Student(String name, int id) {
            this.name = name;
            this.id = id;
        }

        @Override
        public String toString() {
            return "Student(name=" + name + ", id=" + id + ")";
        }
    }

    // Performs Linear Search for Student by id
    public int[] linearSearchObject(Student[] arr, int targetId) {
        int comparisons = 0;
        for (int i = 0; i < arr.length; i++) {
            comparisons++;
            if (arr[i].id == targetId) {
                return new int[]{i, comparisons};
            }
        }
        return new int[]{-1, comparisons};
    }

    // Converts array to string
    public String toString(Student[] arr) {
        StringBuilder result = new StringBuilder("[");
        int limit = Math.min(arr.length, 10); // Limit output for large arrays
        for (int i = 0; i < limit; i++) {
            result.append(arr[i].toString());
            if (i < limit - 1) {
                result.append(", ");
            }
        }
        if (arr.length > limit) {
            result.append(", ...]");
        } else {
            result.append("]");
        }
        return result.toString();
    }

    // Helper class for test cases
    static class TestCase {
        Student[] arr;
        int targetId;
        String description;

        TestCase(Student[] arr, int targetId, String description) {
            this.arr = arr;
            this.targetId = targetId;
            this.description = description;
        }
    }

    // Main method to test object search
    public static void main(String[] args) {
        LinearSearchObjectSearch searcher = new LinearSearchObjectSearch();

        // Test cases
        TestCase[] testCases = {
            new TestCase(new Student[]{
                new Student("Alice", 101),
                new Student("Bob", 102),
                new Student("Charlie", 101),
                new Student("David", 103),
                new Student("Eve", 104)
            }, 101, "Mixed IDs with duplicates (n=5)"),
            new TestCase(new Student[]{}, 101, "Empty array (n=0)"),
            new TestCase(new Student[]{
                new Student("Frank", 105)
            }, 105, "Single element (n=1)"),
            new TestCase(new Student[]{
                new Student("Grace", 106),
                new Student("Hannah", 107),
                new Student("Ivy", 108),
                new Student("Jack", 109),
                new Student("Kate", 110),
                new Student("Liam", 111)
            }, 112, "Absent ID (n=6)"),
            new TestCase(new Student[]{
                new Student("Mia", 101),
                new Student("Noah", 101),
                new Student("Olivia", 101),
                new Student("Peter", 101)
            }, 101, "Duplicate IDs (n=4, all same)")
        };

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            System.out.println("Test case " + (i + 1) + ": " + testCases[i].description);
            Student[] arr = testCases[i].arr.clone(); // Copy to preserve original
            int targetId = testCases[i].targetId;
            System.out.println("Input Array: " + searcher.toString(arr));
            System.out.println("Target ID: " + targetId);
            int[] result = searcher.linearSearchObject(arr, targetId);
            System.out.println("Index: " + result[0]);
            System.out.println("Comparisons: " + result[1] + "\n");
        }
    }
}

Output

Running the main method produces:

Test case 1: Mixed IDs with duplicates (n=5)
Input Array: [Student(name=Alice, id=101), Student(name=Bob, id=102), Student(name=Charlie, id=101), Student(name=David, id=103), Student(name=Eve, id=104)]
Target ID: 101
Index: 0
Comparisons: 1

Test case 2: Empty array (n=0)
Input Array: []
Target ID: 101
Index: -1
Comparisons: 0

Test case 3: Single element (n=1)
Input Array: [Student(name=Frank, id=105)]
Target ID: 105
Index: 0
Comparisons: 1

Test case 4: Absent ID (n=6)
Input Array: [Student(name=Grace, id=106), Student(name=Hannah, id=107), Student(name=Ivy, id=108), Student(name=Jack, id=109), Student(name=Kate, id=110), Student(name=Liam, id=111)]
Target ID: 112
Index: -1
Comparisons: 6

Test case 5: Duplicate IDs (n=4, all same)
Input Array: [Student(name=Mia, id=101), Student(name=Noah, id=101), Student(name=Olivia, id=101), Student(name=Peter, id=101)]
Target ID: 101
Index: 0
Comparisons: 1

Explanation:

  • Test case 1: Finds first Student with id=101 at index 0 after 1 comparison; duplicates exist later.
  • Test case 2: Empty array returns -1 with 0 comparisons.
  • Test case 3: Single element with matching id=105 found at index 0 after 1 comparison.
  • Test case 4: Scans all 6 elements, returns -1 for absent id=112 after 6 comparisons.
  • Test case 5: Finds first Student with id=101 at index 0 after 1 comparison, despite all having id=101.

How It Works

  • Student Class:
    • Contains name (String) and id (integer).
    • Includes toString for readable output.
  • linearSearchObject:
    • Iterates through the array, incrementing comparisons for each object.
    • Checks if the id matches targetId.
    • Returns [index, comparisons] for the first match or [-1, comparisons] if none.
  • toString: Formats array as a string, limiting to 10 elements.
  • Example Trace (Test case 1, [Alice(101), Bob(102), Charlie(101), David(103), Eve(104)], target=101):
    • Check index 0: Alice.id=101 = 101, comparisons=1, return [0, 1].
  • Main Method: Tests mixed IDs with duplicates, empty array, single element, absent ID, and all duplicate IDs, displaying results and comparisons.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
linearSearchObjectO(n) worst, O(1) bestO(1)
toStringO(n)O(n)

Note:

  • n is the array length.
  • Time complexity: O(n) for linearSearchObject in worst/average cases (full or partial scan); O(1) in best case (target at index 0); O(n) for toString.
  • Space complexity: O(1) for linearSearchObject (constant extra space); O(n) for toString (string builder).
  • Linear Search stops at the first matching id, making it efficient for early matches.

✅ Tip: Linear Search for objects is simple and works on unsorted arrays, ideal for small datasets or when the target is near the start. Use meaningful toString methods for clear output.

⚠ Warning: Linear Search has O(n) time complexity in the worst case, inefficient for large arrays. For sorted arrays or frequent searches, consider binary search or hash-based structures for better performance.