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 Multiple Targets

Problem Statement

Write a Java program that modifies the Linear Search algorithm to return all indices where a target integer appears in an array of integers that may contain duplicates. The program should count the number of comparisons made during the search and test with the array [1, 3, 3, 5, 3] and target 3, as well as arrays of different sizes (e.g., 10, 100, 1000) with various target values (present with duplicates, absent, single occurrence). Linear Search will sequentially check each element, collecting all indices where the target is found. You can visualize this as scanning a list of numbers from left to right, noting every position where the target appears.

Input:

  • An array of integers and a target integer to find. Output: A list of all indices where the target appears (empty list 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.
  • Array elements and target are integers in the range [-10^9, 10^9]. Example:
  • Input: array = [1, 3, 3, 5, 3], target = 3
  • Output:
    • Input Array: [1, 3, 3, 5, 3]
    • Target: 3
    • Indices: [1, 2, 4]
    • Comparisons: 5
  • Explanation: Linear Search checks all elements, finding 3 at indices 1, 2, and 4 after 5 comparisons.
  • Input: array = [1, 2, 3], target = 4
  • Output:
    • Input Array: [1, 2, 3]
    • Target: 4
    • Indices: []
    • Comparisons: 3
  • Explanation: Linear Search checks all elements, returns an empty list as 4 is not found after 3 comparisons.

Pseudocode

FUNCTION linearSearchMultiple(arr, target)
    SET comparisons to 0
    CREATE indices as empty list
    FOR i from 0 to length of arr - 1
        INCREMENT comparisons
        IF arr[i] equals target THEN
            APPEND i to indices
        ENDIF
    ENDFOR
    RETURN indices, comparisons
ENDFUNCTION

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

FUNCTION main()
    SET sizes to [5, 10, 100, 1000]
    SET testCases to array of (array, target) pairs including [1, 3, 3, 5, 3] with target 3
    FOR each testCase in testCases
        PRINT test case details
        SET arr to testCase array
        SET target to testCase target
        CALL linearSearchMultiple(arr, target) to get indices, comparisons
        PRINT input array, target, indices, comparisons
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define linearSearchMultiple: a. Initialize a comparisons counter to 0 and an empty list for indices. b. Iterate through the array from index 0 to n-1. c. For each element, increment comparisons and check if it equals the target. d. If equal, append the index to the indices list. e. Return the indices list and comparisons.
  2. Define toString: a. Convert array to a string, limiting output for large arrays.
  3. In main, test with: a. Specific case: array [1, 3, 3, 5, 3], target 3. b. Array sizes: 10, 100, 1000. c. For each size, test:
    • Target present with duplicates.
    • Target absent.
    • Target with single occurrence. d. Generate random arrays with duplicates using a fixed seed.

Java Implementation

import java.util.*;

public class LinearSearchMultipleTargets {
    // Performs Linear Search for all occurrences and counts comparisons
    public Object[] linearSearchMultiple(int[] arr, int target) {
        int comparisons = 0;
        List<Integer> indices = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            comparisons++;
            if (arr[i] == target) {
                indices.add(i);
            }
        }
        return new Object[]{indices, comparisons};
    }

    // Converts array to string
    public String toString(int[] 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]);
            if (i < limit - 1) {
                result.append(", ");
            }
        }
        if (arr.length > limit) {
            result.append(", ...]");
        } else {
            result.append("]");
        }
        return result.toString();
    }

    // Generates random array with duplicates
    private int[] generateRandomArray(int n) {
        Random rand = new Random(42); // Fixed seed for reproducibility
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = rand.nextInt(11); // [0, 10] to ensure duplicates
        }
        return arr;
    }

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

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

    // Main method to test multiple targets
    public static void main(String[] args) {
        LinearSearchMultipleTargets searcher = new LinearSearchMultipleTargets();
        int[] sizes = {5, 10, 100, 1000};

        // Initialize test cases
        TestCase[] testCases = new TestCase[10];
        // Specific test case
        testCases[0] = new TestCase(new int[]{1, 3, 3, 5, 3}, 3, "Specific case [1, 3, 3, 5, 3], target 3");

        // Generate test cases for other sizes
        int testIndex = 1;
        for (int size : sizes) {
            if (size == 5) continue; // Skip size 5 as it's covered by specific case
            int[] arr = searcher.generateRandomArray(size);
            testCases[testIndex++] = new TestCase(arr, arr[size / 2], "Target present with duplicates");
            testCases[testIndex++] = new TestCase(arr, 1000000, "Target absent");
            testCases[testIndex++] = new TestCase(new int[]{size}, size, "Single occurrence (size=" + size + ")");
        }

        // Run test cases
        for (int i = 0; i < testCases.length; i++) {
            if (testCases[i] == null) break; // Avoid null cases
            System.out.println("Test case " + (i + 1) + ": " + testCases[i].description);
            int[] arr = testCases[i].arr.clone(); // Copy to preserve original
            int target = testCases[i].target;
            System.out.println("Input Array: " + searcher.toString(arr));
            System.out.println("Target: " + target);
            Object[] result = searcher.linearSearchMultiple(arr, target);
            List<Integer> indices = (List<Integer>) result[0];
            int comparisons = (int) result[1];
            System.out.println("Indices: " + indices);
            System.out.println("Comparisons: " + comparisons + "\n");
        }
    }
}

Output

Running the main method produces (example output, random values fixed by seed):

Test case 1: Specific case [1, 3, 3, 5, 3], target 3
Input Array: [1, 3, 3, 5, 3]
Target: 3
Indices: [1, 2, 4]
Comparisons: 5

Test case 2: Target present with duplicates
Input Array: [6, 4, 6, 9, 8, 7, 6, 4, 3, 7]
Target: 8
Indices: [4]
Comparisons: 10

Test case 3: Target absent
Input Array: [6, 4, 6, 9, 8, 7, 6, 4, 3, 7]
Target: 1000000
Indices: []
Comparisons: 10

Test case 4: Single occurrence (size=10)
Input Array: [10]
Target: 10
Indices: [0]
Comparisons: 1

Test case 5: Target present with duplicates
Input Array: [6, 4, 6, 9, 8, 7, 6, 4, 3, 7, ...]
Target: 4
Indices: [1, 7, 15, 22, 30, 36, 44, 50, 58, 66, ...]
Comparisons: 100

Test case 6: Target absent
Input Array: [6, 4, 6, 9, 8, 7, 6, 4, 3, 7, ...]
Target: 1000000
Indices: []
Comparisons: 100

Test case 7: Single occurrence (size=100)
Input Array: [100]
Target: 100
Indices: [0]
Comparisons: 1

Test case 8: Target present with duplicates
Input Array: [6, 4, 6, 9, 8, 7, 6, 4, 3, 7, ...]
Target: 0
Indices: [12, 24, 37, 49, 62, 74, 87, 99, 112, 125, ...]
Comparisons: 1000

Test case 9: Target absent
Input Array: [6, 4, 6, 9, 8, 7, 6, 4, 3, 7, ...]
Target: 1000000
Indices: []
Comparisons: 1000

Test case 10: Single occurrence (size=1000)
Input Array: [1000]
Target: 1000
Indices: [0]
Comparisons: 1

Explanation:

  • Specific case: Finds 3 at indices [1, 2, 4] in [1, 3, 3, 5, 3] after 5 comparisons.
  • Size 10: Finds duplicate target (single occurrence in this case) at index [4] (10 comparisons), absent target (10 comparisons), single occurrence (1 comparison).
  • Size 100: Finds duplicate target at multiple indices (~10 indices, 100 comparisons), absent target (100 comparisons), single occurrence (1 comparison).
  • Size 1000: Finds duplicate target at multiple indices (~100 indices, 1000 comparisons), absent target (1000 comparisons), single occurrence (1 comparison).
  • Always scans entire array to find all occurrences.

How It Works

  • linearSearchMultiple:
    • Initializes comparisons to 0 and an empty ArrayList for indices.
    • Iterates through the array, incrementing comparisons for each element.
    • Appends index to indices when target is found.
    • Returns [indices, comparisons].
  • toString: Formats array, limiting output to 10 elements.
  • generateRandomArray: Creates an array with values in [0, 10] to ensure duplicates.
  • Example Trace (Specific case, [1, 3, 3, 5, 3], target=3):
    • Check index 0: 1 ≠ 3, comparisons=1, indices=[].
    • Check index 1: 3 = 3, comparisons=2, indices=[1].
    • Check index 2: 3 = 3, comparisons=3, indices=[1, 2].
    • Check index 3: 5 ≠ 3, comparisons=4, indices=[1, 2].
    • Check index 4: 3 = 3, comparisons=5, indices=[1, 2, 4].
    • Return [[1, 2, 4], 5].
  • Main Method: Tests specific case [1, 3, 3, 5, 3] with target 3, and sizes 10, 100, 1000 with duplicates, absent, and single-occurrence targets.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
linearSearchMultipleO(n)O(n) worst
toStringO(n)O(n)
generateRandomArrayO(n)O(n)

Note:

  • n is the array length.
  • Time complexity: O(n) for linearSearchMultiple (always scans entire array); O(n) for toString and generateRandomArray.
  • Space complexity: O(n) for linearSearchMultiple in worst case (all elements match target); O(n) for toString (string builder) and generateRandomArray (array storage).
  • Always performs n comparisons to find all occurrences.

✅ Tip: Linear Search for multiple targets is useful for unsorted arrays with duplicates. Use an ArrayList to dynamically store indices, and test with small value ranges to ensure duplicates.

⚠ Warning: Linear Search always requires O(n) comparisons to find all occurrences, even if matches are found early. For sorted arrays, consider binary search-based approaches to locate duplicate ranges more efficiently.