Common Algorithms

Linear Search

Finding a specific item in a collection is one of the most common programming tasks, from looking up a user in a database to checking if an email exists in a list. Linear search provides a straightforward approach that works on any list, checking each element one by one until the target is found.

Predicate Search

basic.py 
# Basic linear search


def linear_search(arr, target):
    """Search for target in array, return index or -1"""
    # Search each element sequentially
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # found - return index
    return -1  # not found


# Test linear search
numbers = 

print("List:", numbers)
print("Search 8:", linear_search(numbers, 8))
print("Search 1:", linear_search(numbers, 1))
print("Search 7:", linear_search(numbers, 7))


# Basic linear search


def linear_search(arr, target):
    """Search for target in array, return index or -1"""
    # Search each element sequentially
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # found - return index
    return -1  # not found


# Test linear search
numbers = 

print("List:", numbers)
print("Search 8:", linear_search(numbers, 8))
print("Search 1:", linear_search(numbers, 1))
print("Search 7:", linear_search(numbers, 7))


# Basic linear search


def linear_search(arr, target):
    """Search for target in array, return index or -1"""
    # Search each element sequentially
    for i in range(len(arr)):
        if arr[i] == target:
            return i  # found - return index
    return -1  # not found


# Test linear search
numbers = 

print("List:", numbers)
print("Search 8:", linear_search(numbers, 8))
print("Search 1:", linear_search(numbers, 1))
print("Search 7:", linear_search(numbers, 7))
strings.py 
# Search strings


def search_string(arr, target):
    """Search for exact string match"""
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1


def search_case_insensitive(arr, target):
    """Search ignoring case"""
    # Case-insensitive search
    target_lower = target.lower()
    for i in range(len(arr)):
        if arr[i].lower() == target_lower:
            return i
    return -1


# Test string searches
fruits = ["apple", "banana", "cherry", "date", "elderberry"]

print("Fruits:", fruits)
print("Search 'cherry':", search_string(fruits, "cherry"))
print("Search 'grape':", search_string(fruits, "grape"))

print("\nCase-insensitive:")
print("Search 'BANANA':", search_case_insensitive(fruits, "BANANA"))
print("Search 'Apple':", search_case_insensitive(fruits, "Apple"))
find_all.py 
# Find all occurrences


def find_all(arr, target):
    """Return list of all indices where target appears"""
    indices = []

    # Collect all matching indices
    for i in range(len(arr)):
        if arr[i] == target:
            indices.append(i)

    return indices


# Test finding multiple occurrences
numbers = [3, 7, 3, 9, 3, 1, 3]

print("List:", numbers)
print("All 3's at:", find_all(numbers, 3))
print("All 9's at:", find_all(numbers, 9))
print("All 5's at:", find_all(numbers, 5))
count.py 
# Search with count


def linear_search_counted(arr, target):
    """Return (index, comparisons) tuple"""
    comparisons = 0

    # Count each comparison
    for i in range(len(arr)):
        comparisons += 1
        if arr[i] == target:
            return (i, comparisons)

    return (-1, comparisons)


# Test with different positions
numbers = [10, 20, 30, 40, 50]

idx1, comp1 = linear_search_counted(numbers, 10)  # first element
print(f"Search 10: index={idx1}, comparisons={comp1}")

idx2, comp2 = linear_search_counted(numbers, 50)  # last element
print(f"Search 50: index={idx2}, comparisons={comp2}")

idx3, comp3 = linear_search_counted(numbers, 99)  # not found
print(f"Search 99: index={idx3}, comparisons={comp3}")
predicate.py 
# Search with condition


def find_first(arr, condition):
    """Find first element matching condition function"""
    # Search for first element matching condition
    for i in range(len(arr)):
        if condition(arr[i]):
            return i
    return -1


# Test with different conditions
numbers = [3, 7, 12, 5, 18, 9]

print("List:", numbers)

# Find first even number
even_idx = find_first(numbers, lambda x: x % 2 == 0)
print("First even at index:", even_idx)

# Find first number > 10
large_idx = find_first(numbers, lambda x: x > 10)
print("First > 10 at index:", large_idx)

# Find first negative (not found)
neg_idx = find_first(numbers, lambda x: x < 0)
print("First negative at index:", neg_idx)

Characteristics

  • Time complexity: O(n) - must potentially check every element
  • Space complexity: O(1) - only uses a few variables
  • Works on: unsorted or sorted lists
  • Best case: O(1) - target is first element
  • Worst case: O(n) - target is last element or not present

When to Use

  • Small lists
  • Unsorted data
  • Single search operation
  • When simplicity matters more than speed
sequential_search Examine each element in order from first to last until finding the target
find_all Return all indices where the target appears, not just the first
predicate_search Search using a condition function instead of a specific value
time_complexity O(n) - must potentially check every element in the worst case

Exercise: practical.py

Implement a search function that finds products by name in a shopping cart and returns their total price