• Concept and explanation

• Dry run

• Time and space complexity

• Java code

• Real-life analogy

• Problem-solving patterns where linear search is used

• Problem-based examples with Java code

Linear Search

Concept

Linear Search (also known as Sequential Search) is the most basic search algorithm. It works by:

• Traversing each element in the array or list from the beginning to the end

• Comparing the current element to the target

• Returning the index if a match is found

• If no match is found by the end, returning -1

Linear search can be used on unsorted data, making it flexible but inefficient for large datasets.

Dry Run

Input:
arr = [7, 3, 9, 1, 6]
target = 9

Steps:

1. Compare 7 with 9 → not equal

2. Compare 3 with 9 → not equal

3. Compare 9 with 9 → match found at index 2
   Return 2

Time Complexity

Space Complexity

• O(1) – Constant extra space; no additional memory required other than a few variables.

Java Implementation

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

    public static void main(String[] args) {
        int[] nums = {5, 3, 8, 6, 4};
        int target = 6;
        int result = linearSearch(nums, target);
        System.out.println("Element found at index: " + result);
    }
}

Real-Life Analogy

Imagine looking for a specific book in an unorganized pile. You start checking one book at a time from the top. You keep going until you either find the desired book or run out of books to check.

This is how linear search operates — no assumptions are made about the order of data.

Problem-Solving Scenarios and Patterns

Linear search is useful in:

• Very small or unsorted datasets

• One-time lookups in ad hoc arrays

• Data streams where ordering is not guaranteed

• Arrays with frequent insertions/deletions (where maintaining order is inefficient)

Example Problems Using Linear Search

1. Find Index of First Occurrence

Problem:

Return the index of the first occurrence of the target element in an unsorted array.

int findFirstOccurrence(int[] arr, int target) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) return i;
    }
    return -1;
}

2. Count Occurrences of a Target Value

int countOccurrences(int[] arr, int target) {
    int count = 0;
    for (int num : arr) {
        if (num == target) count++;
    }
    return count;
}

3. Check if an Element Exists

boolean exists(int[] arr, int target) {
    for (int num : arr) {
        if (num == target) return true;
    }
    return false;
}

4. Find Maximum in an Unsorted Array

int findMax(int[] arr) {
    int max = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    return max;
}

5. Find All Indices of a Target Value

List<Integer> findAllIndices(int[] arr, int target) {
    List<Integer> indices = new ArrayList<>();
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == target) {
            indices.add(i);
        }
    }
    return indices;
}

Summary