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 Last Occurrence

Problem Statement

Write a Java program that modifies the Linear Search algorithm to find the last occurrence of a target integer 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, 8] and target 3, as well as arrays of different sizes (e.g., 10, 100, 1000) with various target values (present with duplicates, absent, last element). Linear Search will sequentially check each element, updating the result whenever the target is found to ensure the last occurrence is returned. You can visualize this as scanning a list of numbers from left to right, keeping track of the most recent position where the target appears until the end is reached.

Input:

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

Pseudocode

FUNCTION linearSearchLast(arr, target)
    SET comparisons to 0
    SET lastIndex to -1
    FOR i from 0 to length of arr - 1
        INCREMENT comparisons
        IF arr[i] equals target THEN
            SET lastIndex to i
        ENDIF
    ENDFOR
    RETURN lastIndex, 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, 8] with target 3
    FOR each testCase in testCases
        PRINT test case details
        SET arr to testCase array
        SET target to testCase target
        CALL linearSearchLast(arr, target) to get lastIndex, comparisons
        PRINT input array, target, lastIndex, comparisons
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define linearSearchLast: a. Initialize a comparisons counter to 0 and lastIndex to -1. 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, update lastIndex to the current index. e. Return lastIndex 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, 8], target 3. b. Array sizes: 10, 100, 1000. c. For each size, test:
    • Target present with duplicates (middle of duplicates).
    • Target absent (worst case).
    • Target as the last element. d. Generate random arrays with duplicates using a fixed seed.

Java Implementation

import java.util.*;

public class LinearSearchLastOccurrence {
    // Performs Linear Search for last occurrence and counts comparisons
    public int[] linearSearchLast(int[] arr, int target) {
        int comparisons = 0;
        int lastIndex = -1;
        for (int i = 0; i < arr.length; i++) {
            comparisons++;
            if (arr[i] == target) {
                lastIndex = i;
            }
        }
        return new int[]{lastIndex, 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 Linear Search for last occurrence
    public static void main(String[] args) {
        LinearSearchLastOccurrence searcher = new LinearSearchLastOccurrence();
        int[] sizes = {5, 10, 100, 1000};

        // Initialize test cases
        TestCase[] testCases = new TestCase[13];
        // Specific test case
        testCases[0] = new TestCase(new int[]{1, 3, 3, 5, 8}, 3, "Specific case [1, 3, 3, 5, 8], 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 (middle)");
            testCases[testIndex++] = new TestCase(arr, 1000000, "Target absent");
            testCases[testIndex++] = new TestCase(arr, arr[size - 1], "Target last element");
        }

        // 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);
            int[] result = searcher.linearSearchLast(arr, target);
            System.out.println("Last Index: " + result[0]);
            System.out.println("Comparisons: " + result[1] + "\n");
        }
    }
}

Output

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

Test case 1: Specific case [1, 3, 3, 5, 8], target 3
Input Array: [1, 3, 3, 5, 8]
Target: 3
Last Index: 2
Comparisons: 5

Test case 2: Target present with duplicates (middle)
Input Array: [6, 4, 6, 9, 8, 7, 6, 4, 3, 7]
Target: 8
Last Index: 4
Comparisons: 10

Test case 3: Target absent
Input Array: [6, 4, 6, 9, 8, 7, 6, 4, 3, 7]
Target: 1000000
Last Index: -1
Comparisons: 10

Test case 4: Target last element
Input Array: [6, 4, 6, 9, 8, 7, 6, 4, 3, 7]
Target: 7
Last Index: 9
Comparisons: 10

Test case 5: Target present with duplicates (middle)
Input Array: [6, 4, 6, 9, 8, 7, 6, 4, 3, 7, ...]
Target: 4
Last Index: 75
Comparisons: 100

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

Test case 7: Target last element
Input Array: [6, 4, 6, 9, 8, 7, 6, 4, 3, 7, ...]
Target: 2
Last Index: 99
Comparisons: 100

Test case 8: Target present with duplicates (middle)
Input Array: [6, 4, 6, 9, 8, 7, 6, 4, 3, 7, ...]
Target: 0
Last Index: 500
Comparisons: 1000

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

Test case 10: Target last element
Input Array: [6, 4, 6, 9, 8, 7, 6, 4, 3, 7, ...]
Target: 6
Last Index: 999
Comparisons: 1000

Explanation:

  • Specific case: Finds last 3 at index 2 in [1, 3, 3, 5, 8] after 5 comparisons.
  • Size 10: Finds duplicate target in middle (~index 4, 10 comparisons), absent target (10 comparisons), last element (10 comparisons).
  • Size 100: Finds duplicate target (~index 75, 100 comparisons), absent target (100 comparisons), last element (100 comparisons).
  • Size 1000: Finds duplicate target (~index 500, 1000 comparisons), absent target (1000 comparisons), last element (1000 comparisons).
  • Always scans entire array to ensure last occurrence is found.

How It Works

  • linearSearchLast:
    • Initializes comparisons to 0 and lastIndex to -1.
    • Iterates through the array, incrementing comparisons for each element.
    • Updates lastIndex whenever the target is found.
    • Returns [lastIndex, comparisons].
  • toString: Formats array as a string, 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, 8], target=3):
    • Check index 0: 1 ≠ 3, comparisons=1, lastIndex=-1.
    • Check index 1: 3 = 3, comparisons=2, lastIndex=1.
    • Check index 2: 3 = 3, comparisons=3, lastIndex=2.
    • Check index 3: 5 ≠ 3, comparisons=4, lastIndex=2.
    • Check index 4: 8 ≠ 3, comparisons=5, lastIndex=2.
    • Return [2, 5].
  • Main Method: Tests specific case [1, 3, 3, 5, 8] with target 3, and sizes 10, 100, 1000 with targets in the middle (duplicates), absent, and last element.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
linearSearchLastO(n)O(1)
toStringO(n)O(n)
generateRandomArrayO(n)O(n)

Note:

  • n is the array length.
  • Time complexity: O(n) for linearSearchLast (always scans entire array to find last occurrence); O(n) for toString and generateRandomArray.
  • Space complexity: O(1) for linearSearchLast (constant extra space); O(n) for toString (string builder) and generateRandomArray (array storage).
  • Always performs n comparisons to ensure the last occurrence is found.

✅ Tip: Linear Search for the last occurrence ensures all duplicates are considered by scanning the entire array. Use a small range of values to test duplicates effectively.

⚠ Warning: Linear Search for the last occurrence always requires O(n) comparisons, even if the target is found early, as it must check for later occurrences. For sorted arrays, consider binary search modifications for efficiency.