🔍 Linear Search Fundamentals

🎯 What is Linear Search?

Linear search (also called sequential search) is the simplest search algorithm. It checks each element in a collection sequentially until the target is found or the end is reached.

Approach: Check each element one by one
Precondition: No preconditions (works on any collection)
Time Complexity: O(n) worst case, O(1) best case
Space Complexity: O(1) iterative, O(n) recursive

📌 Sequential📌 No Sorting Required📌 Universal

The Core Insight

Key Insight: Linear search is the most intuitive search method. It works on any data structure and doesn't require any preprocessing. While it's slower for large datasets, it's the only option for unsorted or streaming data.

When to Use:

Unsorted Data Arrays, lists, linked lists
Small Datasets When n is small
Streaming Data When data arrives sequentially

# Linear Search - The Simplest Form
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1  # Not found

# Example:
arr = [3, 7, 1, 9, 4, 6, 8]
target = 4
# Returns: 4 (index of 4)

# Visual Walkthrough:
# [3, 7, 1, 9, 4, 6, 8]
#   ^  ^  ^  ^  ^
#   1  2  3  4  ✓ Found at index 4

💻 Basic Implementation

🎯 Standard Linear Search

The basic implementation loops through the array from index 0 to n-1, comparing each element with the target.

Approach: Iterative loop with early exit
Returns: Index of target, or -1 if not found
Edge Cases: Empty array, target at beginning/end

# Basic Linear Search - Multiple Variants

# Variant 1: Return first occurrence
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# Variant 2: Return boolean (found/not found)
def linear_search_bool(arr, target):
    for element in arr:
        if element == target:
            return True
    return False

# Variant 3: With early termination
def linear_search_early(arr, target):
    n = len(arr)
    for i in range(n):
        if arr[i] == target:
            return i
        # Optional: if array is sorted, can break early
    return -1

# Variant 4: Using enumerate
def linear_search_enumerate(arr, target):
    for i, element in enumerate(arr):
        if element == target:
            return i
    return -1

# Example
arr = [5, 2, 8, 1, 9, 3, 7]
print(linear_search(arr, 9))  # 4
print(linear_search(arr, 10)) # -1
print(linear_search_bool(arr, 3))  # True
print(linear_search_bool(arr, 11)) # False

🚀 Sentinel Linear Search

🎯 Faster by Avoiding Boundary Checks

Sentinel linear search reduces comparisons by placing the target at the end of the array, eliminating the need to check for array bounds in each iteration.

Approach: Add sentinel (target) at the end
Time: Slightly faster (removes one comparison per iteration)
Space: O(n) (requires copy of array)
Trade-off: Speed vs memory

# Sentinel Linear Search
def sentinel_linear_search(arr, target):
    n = len(arr)
    
    # Create a copy with sentinel at the end
    arr_copy = arr.copy()
    arr_copy.append(target)  # Sentinel
    
    i = 0
    while arr_copy[i] != target:
        i += 1
    
    # If i reached the sentinel position, target not found
    if i == n:
        return -1
    return i

# Example
arr = [5, 2, 8, 1, 9, 3, 7]
print(sentinel_linear_search(arr, 9))  # 4
print(sentinel_linear_search(arr, 10)) # -1

# Why it's faster:
# Standard loop: 2 comparisons per iteration (i < n and arr[i] == target)
# Sentinel loop: 1 comparison per iteration (arr[i] == target)
# For large arrays, this can be a significant improvement

# Visualization:
# arr = [5, 2, 8, 1, 9, 3, 7, 9]  (sentinel 9 at end)
# Search for 9: i=0,1,2,3,4 → found at i=4
# Search for 10: i=0..7 → found at i=7 (sentinel), then check i==n

📊 Search in Ordered Array

🎯 Optimized Linear Search for Sorted Arrays

If the array is sorted, we can stop early when we pass the target value.

Approach: Stop when arr[i] > target (for ascending order)
Time: O(n) worst, but often faster in practice
Use Case: When array is sorted but small

# Linear Search in Ordered Array
def ordered_linear_search(arr, target):
    # Assumes arr is sorted in ascending order
    for i in range(len(arr)):
        if arr[i] == target:
            return i
        elif arr[i] > target:
            # Since array is sorted, no need to check further
            break
    return -1

# Example
arr = [1, 3, 5, 7, 9, 11, 13, 15]
print(ordered_linear_search(arr, 7))   # 3
print(ordered_linear_search(arr, 10))  # -1 (stops at 11)
print(ordered_linear_search(arr, 0))   # -1 (stops at 1)

# Comparison with regular linear search:
# arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
# Search for 10:
#   Regular: checks all 10 elements
#   Ordered: checks all 10 elements (target at end)
# Search for 0:
#   Regular: checks all 10 elements
#   Ordered: checks 1 element (stops at arr[0] > 0)

📝 Finding All Occurrences

🎯 Find Every Instance of Target

Sometimes we need to find all positions where the target appears, not just the first occurrence.

Approach: Continue searching after finding target
Time: O(n) always (must scan entire array)
Returns: List of indices

# Find All Occurrences
def find_all_occurrences(arr, target):
    positions = []
    for i in range(len(arr)):
        if arr[i] == target:
            positions.append(i)
    return positions

# Alternative: Using enumerate
def find_all_occurrences_enumerate(arr, target):
    return [i for i, val in enumerate(arr) if val == target]

# Count Occurrences
def count_occurrences(arr, target):
    count = 0
    for element in arr:
        if element == target:
            count += 1
    return count

# Example
arr = [1, 2, 3, 2, 4, 2, 5, 2, 6]
print(find_all_occurrences(arr, 2))  # [1, 3, 5, 7]
print(find_all_occurrences(arr, 7))  # []
print(count_occurrences(arr, 2))     # 4
print(count_occurrences(arr, 10))    # 0

# Applications:
# - Finding all occurrences of a word in a text
# - Finding all positions of a character in a string
# - Counting frequencies in datasets

🔄 Recursive Linear Search

🎯 Divide and Conquer Style

Linear search can be implemented recursively, though it's not the most efficient approach.

Approach: Check first element, recurse on rest
Time: O(n) - same as iterative
Space: O(n) due to recursion stack
Use Case: Understanding recursion, functional programming

# Recursive Linear Search
def recursive_linear_search(arr, target, index=0):
    # Base case: end of array
    if index >= len(arr):
        return -1
    
    # Base case: found target
    if arr[index] == target:
        return index
    
    # Recursive case: search in remaining array
    return recursive_linear_search(arr, target, index + 1)

# Tail Recursion Version (more efficient)
def recursive_tail(arr, target, index=0):
    if index >= len(arr):
        return -1
    if arr[index] == target:
        return index
    return recursive_tail(arr, target, index + 1)

# Recursive with slicing (not memory efficient)
def recursive_slice(arr, target):
    if not arr:
        return -1
    if arr[0] == target:
        return 0
    result = recursive_slice(arr[1:], target)
    return -1 if result == -1 else result + 1

# Example
arr = [5, 2, 8, 1, 9, 3, 7]
print(recursive_linear_search(arr, 9))  # 4
print(recursive_linear_search(arr, 10)) # -1

# Comparison:
# Iterative: O(1) space, faster
# Recursive: O(n) space, easier to understand for some

📐 2D Linear Search

🎯 Searching in 2D Arrays

Extend linear search to two-dimensional arrays (matrices).

Approach: Nested loops (row-major or column-major)
Time: O(m × n)
Space: O(1)

# 2D Linear Search
def linear_search_2d(matrix, target):
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            if matrix[i][j] == target:
                return (i, j)
    return None

# Flattened 2D Search (returns flat index)
def linear_search_2d_flat(matrix, target):
    rows = len(matrix)
    cols = len(matrix[0]) if rows > 0 else 0
    
    for i in range(rows):
        for j in range(cols):
            if matrix[i][j] == target:
                return i * cols + j
    return -1

# Find All Occurrences in 2D
def find_all_2d(matrix, target):
    positions = []
    for i in range(len(matrix)):
        for j in range(len(matrix[i])):
            if matrix[i][j] == target:
                positions.append((i, j))
    return positions

# Example
matrix = [
    [1, 2, 3],
    [4, 5, 6],
    [7, 8, 9]
]

print(linear_search_2d(matrix, 5))  # (1, 1)
print(linear_search_2d(matrix, 10)) # None
print(linear_search_2d_flat(matrix, 5))  # 4
print(find_all_2d(matrix, 2))  # [(0, 1)]

🎯 Searching Objects

🎯 Linear Search with Custom Objects

When searching in arrays of objects, we often need to search by a specific attribute.

Approach: Use key extraction function
Flexibility: Search by different attributes
Use Case: Database records, user lists, product catalogs

# Searching Objects by Attribute
class Person:
    def __init__(self, name, age, id):
        self.name = name
        self.age = age
        self.id = id
    
    def __repr__(self):
        return f"Person(name='{self.name}', age={self.age}, id={self.id})"

def search_by_attr(arr, attr_name, target):
    for i, obj in enumerate(arr):
        if getattr(obj, attr_name) == target:
            return i
    return -1

# Using a key function
def search_by_key(arr, key_func, target):
    for i, obj in enumerate(arr):
        if key_func(obj) == target:
            return i
    return -1

# Find all objects matching criteria
def find_all_by_attr(arr, attr_name, target):
    results = []
    for obj in arr:
        if getattr(obj, attr_name) == target:
            results.append(obj)
    return results

# Example
people = [
    Person("Alice", 25, 101),
    Person("Bob", 30, 102),
    Person("Charlie", 25, 103),
    Person("Diana", 35, 104)
]

print(search_by_attr(people, "name", "Bob"))  # 1
print(search_by_attr(people, "age", 25))      # 0 (first match)
print(find_all_by_attr(people, "age", 25))    # [Alice, Charlie]

# Using key function
print(search_by_key(people, lambda p: p.id, 103))  # 2

⚡ Optimizations & Variations

🎯 Making Linear Search Faster

Move-to-Front: Move found element to the front for faster subsequent searches
Transposition: Swap found element one position forward
Frequency Ordering: Reorder by access frequency
Parallel Search: Split array across multiple threads

# Move-to-Front Linear Search
def move_to_front_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            if i > 0:
                # Move to front (swap with first element)
                arr[0], arr[i] = arr[i], arr[0]
                return 0
            return i
    return -1

# Transposition Linear Search
def transposition_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            if i > 0:
                # Swap with previous element
                arr[i], arr[i-1] = arr[i-1], arr[i]
                return i - 1
            return i
    return -1

# Example demonstrating move-to-front
arr = [5, 2, 8, 1, 9, 3, 7]
print(move_to_front_search(arr, 9))  # 4 (original index)
print(arr)  # [9, 2, 8, 1, 5, 3, 7] (9 moved to front)
print(move_to_front_search(arr, 9))  # 0 (now at front!)

# Frequency-based ordering
from collections import Counter

def frequency_ordered_search(arr, target):
    # Count frequencies
    freq = Counter(arr)
    # Sort by frequency (descending)
    arr.sort(key=lambda x: freq[x], reverse=True)
    # Now search in the reordered array
    return linear_search(arr, target)

# Example
arr = [1, 2, 3, 2, 4, 2, 5, 1, 6, 1, 2]
print(frequency_ordered_search(arr, 1))  # Fast because 2 and 1 are most frequent

⏱️ Time & Space Complexities

Variant	Best Case	Average Case	Worst Case	Space
Basic Linear Search	O(1)	O(n)	O(n)	O(1)
Sentinel Search	O(1)	O(n)	O(n)	O(n)
Ordered Search	O(1)	O(n)	O(n)	O(1)
Recursive Search	O(1)	O(n)	O(n)	O(n)
2D Search	O(1)	O(m×n)	O(m×n)	O(1)
Move-to-Front	O(1)	O(n)*	O(n)*	O(1)
Transposition	O(1)	O(n)*	O(n)*	O(1)

* Amortized time with repeated searches

⚖️ Linear vs Binary Search

Feature	Linear Search	Binary Search
Precondition	None	Sorted array
Time Complexity	O(n)	O(log n)
Space Complexity	O(1)	O(1)
Best Case	O(1) (first element)	O(1) (middle element)
Worst Case	O(n) (target at end)	O(log n)
Data Structure	Any	Array (random access)
Implementation	Simple	Moderate
Use Case	Small arrays, unsorted data	Large sorted arrays
Insertion	Easy (O(1) at end)	Hard (O(n) to maintain sort)

# Performance Comparison
import time

def compare_performance(n):
    arr = list(range(n))
    
    # Linear Search (target at end - worst case)
    start = time.time()
    linear_search(arr, n-1)
    linear_time = time.time() - start
    
    # Binary Search (requires sorted array - already sorted)
    import bisect
    start = time.time()
    bisect.bisect_left(arr, n-1)
    binary_time = time.time() - start
    
    print(f"n = {n}")
    print(f"Linear: {linear_time:.6f}s")
    print(f"Binary: {binary_time:.6f}s")
    print(f"Speedup: {linear_time / binary_time:.2f}x")

# Example output for n=1,000,000:
# n = 1000000
# Linear: 0.023456s
# Binary: 0.000012s
# Speedup: 1954.67x

🌍 Real-World Applications

Small Datasets: Searching in configuration files, small lists
Unsorted Data: Real-time data streams, sensor data
Databases: Simple table scans without indexes
Text Processing: Finding characters in strings
User Interfaces: Searching in dropdowns, small lists
File Systems: Searching in small directories
Debugging: Finding elements in arrays during debugging
Educational: Teaching basic algorithms

🧠 Advanced Concepts

Jump Search: Linear search with larger steps (O(√n))
Exponential Search: Find range, then binary search
Interpolation Search: Estimate position based on values
Linear Search in Streams: Processing infinite streams
Probabilistic Search: Search with probability of finding
Parallel Linear Search: Multiple threads searching different segments
Cache-Optimized Search: Memory-aware linear search

📝 Interview Patterns & Problems

🎯 Key Interview Questions

Classic: "Implement linear search to find an element"
All Occurrences: "Find all occurrences of a target"
2D Search: "Search for an element in a matrix"
Min/Max: "Find minimum and maximum using linear scan"
Sentinel: "Implement sentinel linear search"
Move-to-Front: "Optimize repeated searches using move-to-front"
Two Sum: "Find two numbers that sum to target" (linear scan with hash)
Find Missing: "Find missing number using linear scan"

# Interview Problem: Find Minimum and Maximum
def find_min_max(arr):
    if not arr:
        return None
    
    min_val = max_val = arr[0]
    for val in arr[1:]:
        if val < min_val:
            min_val = val
        if val > max_val:
            max_val = val
    
    return min_val, max_val

# Interview Problem: Find Missing Number (1 to n)
def find_missing(arr):
    n = len(arr) + 1
    expected_sum = n * (n + 1) // 2
    actual_sum = sum(arr)
    return expected_sum - actual_sum

# Interview Problem: First Repeating Element
def first_repeating(arr):
    seen = set()
    for val in arr:
        if val in seen:
            return val
        seen.add(val)
    return -1

# Interview Problem: Search in Infinite Array
def search_infinite(arr, target):
    # Exponential search to find bound, then linear/binary
    # (Linear search in the bound)
    idx = 0
    while True:
        try:
            if arr[idx] == target:
                return idx
            idx += 1
        except IndexError:
            break
    return -1

# Interview Problem: Two Sum (using linear scan with hash)
def two_sum(arr, target):
    seen = {}
    for i, val in enumerate(arr):
        complement = target - val
        if complement in seen:
            return [seen[complement], i]
        seen[val] = i
    return []