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

Basic Linear Search

Problem Statement

Write a Java program that implements the Linear Search algorithm to find a target integer in an array of integers. The program should test the implementation with arrays of different sizes (e.g., 10, 100, 1000) and various target values, including cases where the target is present, absent, or the first element, and count the number of comparisons made during each search. Linear Search sequentially checks each element in the array until the target is found or the array is fully traversed. You can visualize this as searching through a list of numbers one by one until you find the desired value or reach the end.

Input:

  • An array of integers and a target integer to find. Output: The index 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 = [64, 34, 25, 12, 22], target = 25
  • Output:
    • Input Array: [64, 34, 25, 12, 22]
    • Target: 25
    • Index: 2
    • Comparisons: 3
  • Explanation: Linear Search checks elements at indices 0, 1, and 2, finding 25 after 3 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 and returns -1 as 4 is not found.

Pseudocode

FUNCTION linearSearch(arr, target)
    SET comparisons to 0
    FOR i from 0 to length of arr - 1
        INCREMENT comparisons
        IF arr[i] equals target 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 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 [10, 100, 1000]
    FOR each size in sizes
        SET testCases to array of (array, target) pairs
        FOR each testCase in testCases
            PRINT test case details
            SET arr to testCase array
            SET target to testCase target
            CALL linearSearch(arr, target) to get index, comparisons
            PRINT input array, target, index, comparisons
        ENDFOR
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define linearSearch: a. Initialize a comparisons counter to 0. 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 found, return the index and comparisons; otherwise, return -1 and comparisons.
  2. Define toString: a. Convert array to a string, e.g., "[64, 34, 25, 12, 22]".
  3. In main, test with: a. Array sizes: 10, 100, 1000. b. For each size, test:
    • Target present in the middle (average case).
    • Target absent (worst case).
    • Target as the first element (best case).
    • Target as a duplicate (if applicable). c. Generate random arrays with a fixed seed for reproducibility.

Java Implementation

import java.util.*;

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

        // Run test cases
        for (int size : sizes) {
            System.out.println("Array Size: " + size);
            int[] baseArray = searcher.generateRandomArray(size);
            TestCase[] testCases = {
                new TestCase(baseArray, baseArray[size / 2], "Target present (middle)"),
                new TestCase(baseArray, 1000000, "Target absent"),
                new TestCase(baseArray, baseArray[0], "Target first element"),
                new TestCase(baseArray, baseArray[size / 4], "Target duplicate (early)")
            };

            for (int i = 0; i < testCases.length; i++) {
                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.linearSearch(arr, target);
                System.out.println("Index: " + result[0]);
                System.out.println("Comparisons: " + result[1] + "\n");
            }
        }
    }
}

Output

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

Array Size: 10
Test case 1: Target present (middle)
Input Array: [727, -333, 648, 374, -767, 360, -766, 304, 289, -628]
Target: 360
Index: 5
Comparisons: 6

Test case 2: Target absent
Input Array: [727, -333, 648, 374, -767, 360, -766, 304, 289, -628]
Target: 1000000
Index: -1
Comparisons: 10

Test case 3: Target first element
Input Array: [727, -333, 648, 374, -767, 360, -766, 304, 289, -628]
Target: 727
Index: 0
Comparisons: 1

Test case 4: Target duplicate (early)
Input Array: [727, -333, 648, 374, -767, 360, -766, 304, 289, -628]
Target: 374
Index: 3
Comparisons: 4

Array Size: 100
Test case 1: Target present (middle)
Input Array: [727, -333, 648, 374, -767, 360, -766, 304, 289, -628, ...]
Target: 672
Index: 50
Comparisons: 51

Test case 2: Target absent
Input Array: [727, -333, 648, 374, -767, 360, -766, 304, 289, -628, ...]
Target: 1000000
Index: -1
Comparisons: 100

Test case 3: Target first element
Input Array: [727, -333, 648, 374, -767, 360, -766, 304, 289, -628, ...]
Target: 727
Index: 0
Comparisons: 1

Test case 4: Target duplicate (early)
Input Array: [727, -333, 648, 374, -767, 360, -766, 304, 289, -628, ...]
Target: 566
Index: 25
Comparisons: 26

Array Size: 1000
Test case 1: Target present (middle)
Input Array: [727, -333, 648, 374, -767, 360, -766, 304, 289, -628, ...]
Target: -626
Index: 500
Comparisons: 501

Test case 2: Target absent
Input Array: [727, -333, 648, 374, -767, 360, -766, 304, 289, -628, ...]
Target: 1000000
Index: -1
Comparisons: 1000

Test case 3: Target first element
Input Array: [727, -333, 648, 374, -767, 360, -766, 304, 289, -628, ...]
Target: 727
Index: 0
Comparisons: 1

Test case 4: Target duplicate (early)
Input Array: [727, -333, 648, 374, -767, 360, -766, 304, 289, -628, ...]
Target: -135
Index: 250
Comparisons: 251

Explanation:

  • Size 10: Finds middle target in 6 comparisons, absent in 10 (full scan), first in 1, duplicate in 4.
  • Size 100: Middle target takes ~51 comparisons, absent 100, first 1, duplicate ~26.
  • Size 1000: Middle target takes ~501 comparisons, absent 1000, first 1, duplicate ~251.
  • Linear Search correctly returns indices and counts comparisons for all cases.

How It Works

  • linearSearch:
    • Iterates through the array, incrementing comparisons for each element check.
    • Returns [index, comparisons] when the target is found or [-1, comparisons] if not found.
  • toString: Formats array as a string, limiting output to 10 elements for large arrays.
  • generateRandomArray: Creates an array with random integers in [-1000, 1000] using a fixed seed.
  • Example Trace (Size 10, Target present, target=360):
    • Array: [727, -333, 648, 374, -767, 360, -766, 304, 289, -628].
    • Check index 0: 727 ≠ 360, comparisons=1.
    • Check index 1: -333 ≠ 360, comparisons=2.
    • Check index 2: 648 ≠ 360, comparisons=3.
    • Check index 3: 374 ≠ 360, comparisons=4.
    • Check index 4: -767 ≠ 360, comparisons=5.
    • Check index 5: 360 = 360, comparisons=6, return [5, 6].
  • Main Method: Tests arrays of sizes 10, 100, 1000 with targets in the middle, absent, first element, and early duplicate, displaying results and comparisons.

Complexity Analysis Table

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

Note:

  • n is the array length.
  • Time complexity: O(n) for linearSearch in worst/average cases (full scan or target near end); O(1) in best case (target at index 0); O(n) for toString and generateRandomArray.
  • Space complexity: O(1) for linearSearch (constant extra space); O(n) for toString (string builder) and generateRandomArray (array storage).
  • Linear Search is simple but inefficient for large arrays compared to binary search.

✅ Tip: Linear Search is easy to implement and works on unsorted arrays, making it suitable for small datasets or when the target is likely near the start. Always count comparisons to understand performance.

⚠ Warning: Linear Search has O(n) time complexity in the worst case, making it inefficient for large arrays. Use binary search for sorted arrays to achieve O(log n) performance.