Linear Search

Linear search is a simple searching algorithm that finds the position of a target value within a list by checking each element sequentially until a match is found or the whole list has been searched.

Algorithm Overview

Linear search works by iterating through each element in the array from left to right and comparing it with the target value. It returns the index of the first occurrence of the target, or -1 if not found.

Key Features

Simple Implementation: Easy to understand and implement
No Prerequisites: Works on both sorted and unsorted arrays
Flexible: Can search any data type that supports equality comparison
Memory Efficient: O(1) space complexity
Multiple Variants: Various implementations for different use cases

Time and Space Complexity

Time Complexity: O(n) where n is the number of elements
Space Complexity: O(1) - uses constant extra space
Best Case: O(1) - target is the first element
Worst Case: O(n) - target is the last element or not present
Average Case: O(n/2) - target is in the middle on average

Usage Examples

Basic Usage

from algo.algorithms.searching.linear_search import linear_search

# Simple search
data = [3, 1, 4, 1, 5, 9, 2, 6]
index = linear_search(data, 5)
print(f"Found 5 at index: {index}")  # Output: Found 5 at index: 4

# Search in strings
names = ['Alice', 'Bob', 'Charlie', 'David']
index = linear_search(names, 'Charlie')
print(f"Found Charlie at index: {index}")  # Output: Found Charlie at index: 2

# Target not found
index = linear_search(data, 10)
print(f"10 not found: {index}")  # Output: 10 not found: -1

Finding All Occurrences

from algo.algorithms.searching.linear_search import linear_search_all

# Find all occurrences of a value
data = [1, 2, 3, 2, 4, 2, 5]
indices = linear_search_all(data, 2)
print(f"Found 2 at indices: {indices}")  # Output: Found 2 at indices: [1, 3, 5]

# Find all occurrences in strings
text = ['cat', 'dog', 'cat', 'bird', 'cat']
indices = linear_search_all(text, 'cat')
print(f"Found 'cat' at indices: {indices}")  # Output: Found 'cat' at indices: [0, 2, 4]

Conditional Search

from algo.algorithms.searching.linear_search import linear_search_with_condition

# Find first even number
data = [1, 3, 5, 8, 9, 10]
index = linear_search_with_condition(data, lambda x: x % 2 == 0)
print(f"First even number at index: {index}")  # Output: First even number at index: 3

# Find first string longer than 5 characters
words = ['cat', 'elephant', 'dog', 'butterfly']
index = linear_search_with_condition(words, lambda s: len(s) > 5)
print(f"First long word at index: {index}")  # Output: First long word at index: 1

# Find first number greater than threshold
data = [1, 3, 5, 7, 9, 11]
index = linear_search_with_condition(data, lambda x: x > 6)
print(f"First number > 6 at index: {index}")  # Output: First number > 6 at index: 3

Backwards Search

from algo.algorithms.searching.linear_search import linear_search_backwards

# Find last occurrence by searching backwards
data = [1, 2, 3, 2, 5, 2, 7]
index = linear_search_backwards(data, 2)
print(f"Last occurrence of 2 at index: {index}")  # Output: Last occurrence of 2 at index: 5

# Compare with forward search
forward_index = linear_search(data, 2)
print(f"First occurrence at: {forward_index}")  # Output: First occurrence at: 1
print(f"Last occurrence at: {index}")  # Output: Last occurrence at: 5

Educational Verbose Search

from algo.algorithms.searching.linear_search import linear_search_verbose

# Educational version that shows each step
data = [10, 20, 30, 40, 50]
index = linear_search_verbose(data, 30)

# Output:
# Searching for 30 in array: [10, 20, 30, 40, 50]
# Step 1: Checking index 0, value = 10 -> No match, continue searching...
# Step 2: Checking index 1, value = 20 -> No match, continue searching...
# Step 3: Checking index 2, value = 30 -> MATCH! Found 30 at index 2

Performance Characteristics

When Linear Search is Optimal

Small datasets: For arrays with fewer than ~100 elements, the overhead of sorting for binary search may not be worth it
Unsorted data: When data cannot be sorted or maintaining sort order is expensive
Infrequent searches: When you search rarely, the cost of sorting isn't justified
Memory-constrained environments: Linear search has minimal memory overhead

Performance Comparison

import time
from algo.algorithms.searching.linear_search import linear_search

# Performance test
large_data = list(range(10000))
target = 7500

# Time linear search
start_time = time.time()
for _ in range(1000):
    linear_search(large_data, target)
linear_time = time.time() - start_time

print(f"Linear search time: {linear_time:.4f}s")

Data Type Support

Linear search works with any data type that supports equality comparison:

# Numbers
linear_search([1, 2, 3, 4, 5], 3)

# Strings
linear_search(['apple', 'banana', 'cherry'], 'banana')

# Floats
linear_search([1.1, 2.2, 3.3], 2.2)

# Custom objects
class Person:
    def __init__(self, name, age):
        self.name = name
        self.age = age

    def __eq__(self, other):
        return isinstance(other, Person) and self.name == other.name

people = [Person('Alice', 30), Person('Bob', 25)]
target = Person('Alice', 35)  # Note: only name matters for equality
index = linear_search(people, target)  # Finds Alice

Edge Cases and Error Handling

Linear search handles various edge cases gracefully:

# Empty array
result = linear_search([], 5)  # Returns -1

# Single element - found
result = linear_search([42], 42)  # Returns 0

# Single element - not found
result = linear_search([42], 5)  # Returns -1

# None values
result = linear_search([1, None, 3], None)  # Returns 1

# Mixed types (not recommended but works)
result = linear_search([1, 'hello', 3.14], 'hello')  # Returns 1

Best Practices

Use appropriate variant: Choose the right function for your use case
Consider data size: For large datasets that are searched frequently, consider sorting and using binary search
Handle edge cases: Always check for -1 return value when target might not exist
Type consistency: Ensure array elements and target are comparable
Performance monitoring: Profile your code to determine if linear search is the bottleneck

Common Pitfalls

Assuming sorted data: Linear search doesn't require sorted data, but don't use it when you have sorted data and need optimal performance
Ignoring return value: Always check if the result is -1 (not found)
Type mismatches: Ensure target type matches array element types
Modifying during search: Don't modify the array while searching (especially with sentinel search)

Algorithm Variants Summary

Function	Use Case	Returns	Time Complexity
`linear_search`	Find first occurrence	Index or -1	O(n)
`linear_search_all`	Find all occurrences	List of indices	O(n)
`linear_search_with_condition`	Custom search logic	Index or -1	O(n)
`linear_search_backwards`	Find last occurrence	Index or -1	O(n)
`linear_search_sentinel`	Optimized search	Index or -1	O(n)
`linear_search_verbose`	Educational/debugging	Index or -1	O(n)

API Reference

Linear Search Algorithm Implementation

Linear search (also called sequential search) is a simple searching algorithm that finds the position of a target value within a list by checking each element of the list sequentially until a match is found or the whole list has been searched.

Time Complexity: O(n) - where n is the number of elements

Space Complexity: O(1) - uses constant extra space

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

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

Characteristics:

Works on both sorted and unsorted arrays
Simple to implement and understand
No preprocessing required
Can be used on any data structure that supports sequential access

`linear_search(arr, target)`

Search for a target value in an array using linear search.

The algorithm iterates through each element in the array from left to right and compares it with the target value. Returns the index of the first occurrence of the target, or -1 if not found.

Parameters:

Name	Type	Description	Default
`arr`	`List[T]`	List of elements to search through	required
`target`	`T`	Value to search for	required

Returns:

Type	Description
`int`	Index of the first occurrence of target, or -1 if not found

Examples:

>>> linear_search([1, 3, 5, 7, 9], 5)
2

>>> linear_search(['apple', 'banana', 'cherry'], 'banana')
1

>>> linear_search([1, 2, 3], 4)
-1

>>> linear_search([], 1)
-1

`linear_search_all(arr, target)`

Find all occurrences of a target value in an array.

This variant returns a list of all indices where the target value appears, rather than just the first occurrence.

Parameters:

Name	Type	Description	Default
`arr`	`List[T]`	List of elements to search through	required
`target`	`T`	Value to search for	required

Returns:

Type	Description
`List[int]`	List of indices where target appears (empty list if not found)

Examples:

>>> linear_search_all([1, 2, 3, 2, 5, 2], 2)
[1, 3, 5]

>>> linear_search_all(['a', 'b', 'a', 'c'], 'a')
[0, 2]

>>> linear_search_all([1, 2, 3], 4)
[]

`linear_search_backwards(arr, target)`

Search for a target value starting from the end of the array.

This variant searches from right to left, which can be useful when you expect the target to be near the end of the array.

Parameters:

Name	Type	Description	Default
`arr`	`List[T]`	List of elements to search through	required
`target`	`T`	Value to search for	required

Returns:

Type	Description
`int`	Index of the last occurrence of target, or -1 if not found

Examples:

>>> linear_search_backwards([1, 2, 3, 2, 5], 2)
3

>>> linear_search_backwards(['a', 'b', 'c'], 'b')
1

>>> linear_search_backwards([1, 2, 3], 4)
-1

`linear_search_sentinel(arr, target)`

Linear search using sentinel technique for slight optimization.

This version adds the target as a sentinel at the end of the array to eliminate the need for bounds checking in the loop. Note: this modifies the input array temporarily.

Parameters:

Name	Type	Description	Default
`arr`	`List[T]`	List of elements to search through (will be modified temporarily)	required
`target`	`T`	Value to search for	required

Returns:

Type	Description
`int`	Index of target, or -1 if not found

Note

This implementation temporarily modifies the input array but restores it before returning. Use with caution in multi-threaded environments.

Examples:

>>> arr = [1, 3, 5, 7, 9]
>>> linear_search_sentinel(arr, 5)
2
>>> arr  # Array is restored
[1, 3, 5, 7, 9]

`linear_search_verbose(arr, target)`

Linear search with detailed step-by-step output for educational purposes.

This version prints each comparison made during the search to help understand how the algorithm works.

Parameters:

Name	Type	Description	Default
`arr`	`List[T]`	List of elements to search through	required
`target`	`T`	Value to search for	required

Returns:

Type	Description
`int`	Index of target, or -1 if not found

`linear_search_with_condition(arr, condition)`

Search for the first element that satisfies a given condition.

This is a more general version of linear search that allows searching based on a custom condition function rather than exact equality.

Parameters:

Name	Type	Description	Default
`arr`	`List[T]`	List of elements to search through	required
`condition`	`Callable[[T], bool]`	Function that returns True for the desired element	required

Returns:

Type	Description
`int`	Index of the first element satisfying the condition, or -1 if none found

Examples:

>>> linear_search_with_condition([1, 3, 5, 7, 9], lambda x: x > 5)
3

>>> linear_search_with_condition(['apple', 'banana', 'cherry'], lambda s: len(s) > 5)
1

>>> linear_search_with_condition([1, 2, 3], lambda x: x > 10)
-1