Linear Search Algorithm

Linear search is the most basic and intuitive searching algorithm. It finds a target value within a list by checking every element one by one, from the beginning to the end, until the target is found or all elements have been examined.

Interactive Visualization

Linear Search Visualization

Target:

Speed: 800ms

Status: Click "Search" to start linear search visualization

Array Visualization

Not Checked

Currently Checking

Found Target

How Linear Search Works:

• Sequential Check: Examine each element one by one from left to right

• Compare: Check if current element equals the target value

• Early Exit: Stop immediately when target is found

• Complete Scan: If not found, check all elements

• Time Complexity: O(n) - may need to check all elements

• Space Complexity: O(1) - no additional memory needed

• Best Case: O(1) - target is the first element

• Worst Case: O(n) - target is last or not present

How Linear Search Works

Linear search, also known as sequential search, is the simplest searching algorithm. It works by examining each element in the list one after another until either the target element is found or the end of the list is reached.

1. Start

Begin at the first element of the array (index 0)

2. Compare

Check if the current element equals the target value

3. Continue or Stop

If found, return index; if not, move to next element

🔍 Sequential Element Checking Process

Step-by-Step Process

Initialize: Set index i = 0 (start at first element)

Compare: Check if arr[i] == target

Found: If match found, return index i

Continue: If no match, increment i and repeat from step 2

Not Found: If i reaches array length, return -1

Example: Searching for 7 in [4, 2, 7, 1, 9]

Step 1: Check arr[0] = 4. Is 4 == 7? No, continue.

Step 2: Check arr[1] = 2. Is 2 == 7? No, continue.

Step 3: Check arr[2] = 7. Is 7 == 7? Yes! Return index 2.

✅ Advantages

• Simple to understand and implement
• Works on unsorted arrays
• No preprocessing required
• Uses constant extra space O(1)
• Can find all occurrences easily

❌ Disadvantages

• Inefficient for large datasets
• Always O(n) time complexity
• No early termination optimization
• Not suitable for repeated searches
• Slower than binary search on sorted data

Pseudocode

ALGORITHM LinearSearch(arr[], n, target)
BEGIN
    // Iterate through each element in the array
    FOR i = 0 TO n-1 DO
        // Check if current element matches target
        IF arr[i] == target THEN
            RETURN i          // Return index where target is found
        END IF
    END FOR
    
    // Target not found in array
    RETURN -1                 // Return -1 to indicate not found
END

Complexity Analysis

Metric	Best Case	Average Case	Worst Case
Time Complexity	O(1)	O(n)	O(n)
Space Complexity	O(1)	O(1)	O(1)
Comparisons	1	n/2	n

Best Case O(1)

• Scenario: Target is the first element
• Comparisons: Only 1 comparison needed
• Example: Searching for 4 in [4, 2, 7, 1, 9]

Average Case O(n)

• Scenario: Target is somewhere in the middle
• Comparisons: Approximately n/2 comparisons
• Assumption: Target is equally likely to be anywhere

Worst Case O(n)

• Scenario: Target is last element or not present
• Comparisons: All n elements must be checked
• Example: Searching for 9 in [4, 2, 7, 1, 9]

Why O(1) Space Complexity?

Linear search uses only a constant amount of extra memory regardless of input size. We only need a few variables (like the loop counter and target value) that don't scale with the array size, making it very memory-efficient.

Code Examples

Here are implementations of linear search in different programming languages. Each version demonstrates the sequential checking process with clear, readable code.

 def linear_search(arr, target):
    """
    Search for a target value in a list using linear search.
    
    Args:
        arr: List of elements to search through
        target: The value to search for
    
    Returns:
        int: Index of target if found, -1 if not found
    
    Time Complexity: O(n)
    Space Complexity: O(1)
    """
    # Check each element one by one
    for i in range(len(arr)):
        # If current element matches target, return its index
        if arr[i] == target:
            return i
    
    # Target not found in the array
    return -1

def linear_search_with_details(arr, target):
    """
    Linear search with detailed step-by-step output.
    """
    print(f"Searching for {target} in array: {arr}")
    
    for i in range(len(arr)):
        print(f"Step {i + 1}: Checking arr[{i}] = {arr[i]}")
        
        if arr[i] == target:
            print(f"Found {target} at index {i}!")
            return i
        else:
            print(f"{arr[i]} != {target}, continue searching...")
    
    print(f"{target} not found in the array.")
    return -1

# Example usage
if __name__ == "__main__":
    numbers = [4, 2, 7, 1, 9, 5, 3, 8, 6]
    target = 5
    
    result = linear_search(numbers, target)
    
    if result != -1:
        print(f"Element {target} found at index {result}")
    else:
        print(f"Element {target} not found in the array")
    
    # Demonstrate with detailed output
    print("\nDetailed search:")
    linear_search_with_details(numbers, 7) 
 public class LinearSearch {
    
    /**
     * Search for a target value in an array using linear search.
     * 
     * @param arr The array to search through
     * @param target The value to search for
     * @return Index of target if found, -1 if not found
     * 
     * Time Complexity: O(n)
     * Space Complexity: O(1)
     */
    public static int linearSearch(int[] arr, int target) {
        // Check each element one by one
        for (int i = 0; i < arr.length; i++) {
            // If current element matches target, return its index
            if (arr[i] == target) {
                return i;
            }
        }
        
        // Target not found in the array
        return -1;
    }
    
    /**
     * Linear search with detailed step-by-step output.
     */
    public static int linearSearchWithDetails(int[] arr, int target) {
        System.out.println("Searching for " + target + " in array: " + 
                          java.util.Arrays.toString(arr));
        
        for (int i = 0; i < arr.length; i++) {
            System.out.println("Step " + (i + 1) + ": Checking arr[" + i + "] = " + arr[i]);
            
            if (arr[i] == target) {
                System.out.println("Found " + target + " at index " + i + "!");
                return i;
            } else {
                System.out.println(arr[i] + " != " + target + ", continue searching...");
            }
        }
        
        System.out.println(target + " not found in the array.");
        return -1;
    }
    
    /**
     * Generic linear search that works with any Comparable type
     */
    public static <T> int linearSearch(T[] arr, T target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i].equals(target)) {
                return i;
            }
        }
        return -1;
    }
    
    /**
     * Helper method to print an array
     */
    public static void printArray(int[] arr) {
        System.out.println(java.util.Arrays.toString(arr));
    }
    
    public static void main(String[] args) {
        int[] numbers = {4, 2, 7, 1, 9, 5, 3, 8, 6};
        int target = 5;
        
        System.out.print("Array: ");
        printArray(numbers);
        
        int result = linearSearch(numbers, target);
        
        if (result != -1) {
            System.out.println("Element " + target + " found at index " + result);
        } else {
            System.out.println("Element " + target + " not found in the array");
        }
        
        // Demonstrate with detailed output
        System.out.println("\nDetailed search:");
        linearSearchWithDetails(numbers, 7);
    }
} 
 #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

/**
 * Search for a target value in a vector using linear search.
 * 
 * @param arr The vector to search through
 * @param target The value to search for
 * @return Index of target if found, -1 if not found
 * 
 * Time Complexity: O(n)
 * Space Complexity: O(1)
 */
int linearSearch(const vector<int>& arr, int target) {
    // Check each element one by one
    for (int i = 0; i < arr.size(); i++) {
        // If current element matches target, return its index
        if (arr[i] == target) {
            return i;
        }
    }
    
    // Target not found in the array
    return -1;
}

/**
 * Helper function to print a vector
 */
void printArray(const vector<int>& arr) {
    cout << "[";
    for (int i = 0; i < arr.size(); i++) {
        cout << arr[i];
        if (i < arr.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
}

/**
 * Linear search with detailed step-by-step output.
 */
int linearSearchWithDetails(const vector<int>& arr, int target) {
    cout << "Searching for " << target << " in array: ";
    printArray(arr);
    
    for (int i = 0; i < arr.size(); i++) {
        cout << "Step " << (i + 1) << ": Checking arr[" << i << "] = " << arr[i] << endl;
        
        if (arr[i] == target) {
            cout << "Found " << target << " at index " << i << "!" << endl;
            return i;
        } else {
            cout << arr[i] << " != " << target << ", continue searching..." << endl;
        }
    }
    
    cout << target << " not found in the array." << endl;
    return -1;
}

/**
 * Template function for linear search that works with any type
 */
template<typename T>
int linearSearch(const vector<T>& arr, const T& target) {
    for (int i = 0; i < arr.size(); i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

int main() {
    vector<int> numbers = {4, 2, 7, 1, 9, 5, 3, 8, 6};
    int target = 5;
    
    cout << "Array: ";
    printArray(numbers);
    
    int result = linearSearch(numbers, target);
    
    if (result != -1) {
        cout << "Element " << target << " found at index " << result << endl;
    } else {
        cout << "Element " << target << " not found in the array" << endl;
    }
    
    // Demonstrate with detailed output
    cout << "\nDetailed search:" << endl;
    linearSearchWithDetails(numbers, 7);
    
    return 0;
} 

When to Use Linear Search

Ideal Use Cases

• Small Datasets: When array size is small (n < 100)
• Unsorted Data: When data is not sorted and sorting is expensive
• One-time Search: When you only need to search once
• Simple Implementation: When code simplicity is more important than efficiency
• Memory Constraints: When you need minimal memory usage

Avoid When

• Large Datasets: When array size is very large (n > 1000)
• Sorted Data Available: When binary search can be used instead
• Frequent Searches: When you need to search the same data multiple times
• Performance Critical: When search speed is the primary concern

Real-World Applications

Common Uses: Finding items in small lists, searching through configuration files, simple database queries, checking if element exists

Better Alternatives: Binary search for sorted data, hash tables for fast lookups, indexed databases for large datasets, tries for string searches