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.

Linear search checks each element in a list sequentially until finding the target or reaching the end. It works on both sorted and unsorted lists.

Algorithm

  1. Start at the first element
  2. Compare each element with the target
  3. If found, return the index
  4. If not found after checking all elements, return -1
sequential_search Examine each element in order from first to last until finding the target

Basic Implementation

numbers
basic.py
Replay: real traced execution (multi-file project)
# 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 = [5, 2, 8, 1, 9, 3]

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 = [4, 7, 2, 7]

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 = [10, 20, 30]

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

  1. numbers ← [5, 2, 8, 1, 9, 3]

    13# Test linear search14numbers→ [5, 2, 8, 1, 9, 3] = [5, 2, 8, 1, 9, 3]15#@numbers=[4, 7, 2, 7], [10, 20, 30]1617print("List:", numbers[5, 2, 8, 1, 9, 3])18print("Search 8:", linear_search(numbers[5, 2, 8, 1, 9, 3], 8))19print("Search 1:", linear_search(numbers, 1))
    outputList: [5, 2, 8, 1, 9, 3]

  2. def linear_search(arr, target):

    pass 1 of 3
    4def linear_search(arr[5, 2, 8, 1, 9, 3], target8):5    """Search for target in array, return index or -1"""6    # Search each element sequentially
    All 3 passes — pass 1 is the card above
    passtargetarr[i]i
    1882
    2113
    37——

  3. for i in range(len(arr)):

    pass 1 of 13
    6# Search each element sequentially7for i0 in range(len(arr[5, 2, 8, 1, 9, 3])):8    if arr[i] == target:9        return i  # found - return index
    13 passes — pass 1 is the card above
    passiarr[i]target
    10——
    21——
    3288
    40——
    51——
    62——
    7311
    80——
    91——
    ⋯ 2 more passes ⋯
    124——
    135——

  4. if arr[i] == target:

    pass 1 of 2
    7for i in range(len(arr)):8    if arr[i]8 == target8:9        return i2  # found - return index10return -1  # not found

  5. print("Search 8:", linear_search(numbers, 8))

    17print("List:", numbers)18print("Search 8:", linear_search(numbers[5, 2, 8, 1, 9, 3], 8))19print("Search 1:", linear_search(numbers[5, 2, 8, 1, 9, 3], 1))20print("Search 7:", linear_search(numbers, 7))
    outputSearch 8: 2

  6. if arr[i] == target:

    pass 2 of 2
    7for i in range(len(arr)):8    if arr[i]1 == target1:9        return i3  # found - return index10return -1  # not found

  7. print("Search 1:", linear_search(numbers, 1))

    18print("Search 8:", linear_search(numbers, 8))19print("Search 1:", linear_search(numbers[5, 2, 8, 1, 9, 3], 1))20print("Search 7:", linear_search(numbers[5, 2, 8, 1, 9, 3], 7))
    outputSearch 1: 3

  8. return -1 # not found

    9        return i  # found - return index10return -1  # not found

  9. print("Search 7:", linear_search(numbers, 7))

    19print("Search 1:", linear_search(numbers, 1))20print("Search 7:", linear_search(numbers[5, 2, 8, 1, 9, 3], 7))
    outputSearch 7: -1

  1. numbers ← [4, 7, 2, 7]

    13# Test linear search14numbers→ [4, 7, 2, 7] = [4, 7, 2, 7]1516print("List:", numbers[4, 7, 2, 7])17print("Search 8:", linear_search(numbers[4, 7, 2, 7], 8))18print("Search 1:", linear_search(numbers, 1))
    outputList: [4, 7, 2, 7]

  2. def linear_search(arr, target):

    pass 1 of 3
    4def linear_search(arr[4, 7, 2, 7], target8):5    """Search for target in array, return index or -1"""6    # Search each element sequentially
    All 3 passes — pass 1 is the card above
    passtargetarr[i]i
    18——
    21——
    3771

  3. for i in range(len(arr)):

    pass 1 of 10
    6# Search each element sequentially7for i0 in range(len(arr[4, 7, 2, 7])):8    if arr[i] == target:9        return i  # found - return index
    All 10 passes — pass 1 is the card above
    passiarr[i]target
    10——
    21——
    32——
    43——
    50——
    61——
    72——
    83——
    90——
    10177

  4. return -1 # not found

    9        return i  # found - return index10return -1  # not found

  5. print("Search 8:", linear_search(numbers, 8))

    16print("List:", numbers)17print("Search 8:", linear_search(numbers[4, 7, 2, 7], 8))18print("Search 1:", linear_search(numbers[4, 7, 2, 7], 1))19print("Search 7:", linear_search(numbers, 7))
    outputSearch 8: -1

  6. return -1 # not found

    9        return i  # found - return index10return -1  # not found

  7. print("Search 1:", linear_search(numbers, 1))

    17print("Search 8:", linear_search(numbers, 8))18print("Search 1:", linear_search(numbers[4, 7, 2, 7], 1))19print("Search 7:", linear_search(numbers[4, 7, 2, 7], 7))
    outputSearch 1: -1

  8. if arr[i] == target:

    7for i in range(len(arr)):8    if arr[i]7 == target7:9        return i1  # found - return index10return -1  # not found

  9. print("Search 7:", linear_search(numbers, 7))

    18print("Search 1:", linear_search(numbers, 1))19print("Search 7:", linear_search(numbers[4, 7, 2, 7], 7))
    outputSearch 7: 1

  1. numbers ← [10, 20, 30]

    13# Test linear search14numbers→ [10, 20, 30] = [10, 20, 30]1516print("List:", numbers[10, 20, 30])17print("Search 8:", linear_search(numbers[10, 20, 30], 8))18print("Search 1:", linear_search(numbers, 1))
    outputList: [10, 20, 30]

  2. def linear_search(arr, target):

    pass 1 of 3
    4def linear_search(arr[10, 20, 30], target8):5    """Search for target in array, return index or -1"""6    # Search each element sequentially
    All 3 passes — pass 1 is the card above
    passtarget
    18
    21
    37

  3. for i in range(len(arr)):

    pass 1 of 9
    6# Search each element sequentially7for i0 in range(len(arr[10, 20, 30])):8    if arr[i] == target:9        return i  # found - return index
    All 9 passes — pass 1 is the card above
    passi
    10
    21
    32
    40
    51
    62
    70
    81
    92

  4. return -1 # not found

    9        return i  # found - return index10return -1  # not found

  5. print("Search 8:", linear_search(numbers, 8))

    16print("List:", numbers)17print("Search 8:", linear_search(numbers[10, 20, 30], 8))18print("Search 1:", linear_search(numbers[10, 20, 30], 1))19print("Search 7:", linear_search(numbers, 7))
    outputSearch 8: -1

  6. return -1 # not found

    9        return i  # found - return index10return -1  # not found

  7. print("Search 1:", linear_search(numbers, 1))

    17print("Search 8:", linear_search(numbers, 8))18print("Search 1:", linear_search(numbers[10, 20, 30], 1))19print("Search 7:", linear_search(numbers[10, 20, 30], 7))
    outputSearch 1: -1

  8. return -1 # not found

    9        return i  # found - return index10return -1  # not found

  9. print("Search 7:", linear_search(numbers, 7))

    18print("Search 1:", linear_search(numbers, 1))19print("Search 7:", linear_search(numbers[10, 20, 30], 7))
    outputSearch 7: -1

Searching Strings

strings.py
Replay: real traced execution (multi-file project)
# 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"))

  1. fruits ← ['apple', 'banana', 'cherry', 'date', 'elderberry']

    22# Test string searches23fruits→ ['apple', 'banana', 'cherry', 'date', 'elderberry'] = ["apple", "banana", "cherry", "date", "elderberry"]2425print("Fruits:", fruits['apple', 'banana', 'cherry', 'date', 'elderberry'])26print("Search 'cherry':", search_string(fruits['apple', 'banana', 'cherry', 'date', 'elderberry'], "cherry"))27print("Search 'grape':", search_string(fruits, "grape"))
    outputFruits: ['apple', 'banana', 'cherry', 'date', 'elderberry']

  2. def search_string(arr, target):

    pass 1 of 2
    4def search_string(arr['apple', 'banana', 'cherry', 'date', 'elderberry'], targetcherry):5    """Search for exact string match"""6    for i in range(len(arr)):

  3. for i in range(len(arr)):

    pass 1 of 8
    5"""Search for exact string match"""6for i0 in range(len(arr['apple', 'banana', 'cherry', 'date', 'elderberry'])):7    if arr[i] == target:8        return i
    All 8 passes — pass 1 is the card above
    passiarr[i]target
    10——
    21——
    32cherrycherry
    40——
    51——
    62——
    73——
    84——

  4. if arr[i] == target:

    6for i in range(len(arr)):7    if arr[i]cherry == targetcherry:8        return i29return -1

  5. print("Search 'cherry':", search_string(fruits, "cherry"))

    25print("Fruits:", fruits)26print("Search 'cherry':", search_string(fruits['apple', 'banana', 'cherry', 'date', 'elderberry'], "cherry"))27print("Search 'grape':", search_string(fruits['apple', 'banana', 'cherry', 'date', 'elderberry'], "grape"))
    outputSearch 'cherry': 2

  6. def search_string(arr, target):

    pass 2 of 2
    4def search_string(arr['apple', 'banana', 'cherry', 'date', 'elderberry'], targetgrape):5    """Search for exact string match"""6    for i in range(len(arr)):

  7. return -1

    8        return i9return -1

  8. print("Search 'grape':", search_string(fruits, "grape"))

    26print("Search 'cherry':", search_string(fruits, "cherry"))27print("Search 'grape':", search_string(fruits['apple', 'banana', 'cherry', 'date', 'elderberry'], "grape"))2829print("\nCase-insensitive:")30print("Search 'BANANA':", search_case_insensitive(fruits['apple', 'banana', 'cherry', 'date', 'elderberry'], "BANANA"))31print("Search 'Apple':", search_case_insensitive(fruits, "Apple"))
    outputSearch 'grape': -1

Case-insensitive:

  9. target_lower ← banana

    pass 1 of 2
    12def search_case_insensitive(arr['apple', 'banana', 'cherry', 'date', 'elderberry'], targetBANANA):13    """Search ignoring case"""14    # Case-insensitive search15    target_lower→ banana = targetBANANA.lower()16    for i in range(len(arr)):

  10. for i in range(len(arr)):

    pass 1 of 3
    15target_lower = target.lower()16for i0 in range(len(arr['apple', 'banana', 'cherry', 'date', 'elderberry'])):17    if arr[i].lower() == target_lower:18        return i
    All 3 passes — pass 1 is the card above
    passiarr[i]target_lower
    10——
    21bananabanana
    30appleapple

  11. if arr[i].lower() == target_lower:

    pass 1 of 2
    16for i in range(len(arr)):17    if arr[i]banana.lower() == target_lowerbanana:18        return i119return -1

  12. print("Search 'BANANA':", search_case_insensitive(fruits, "BANANA"))

    29print("\nCase-insensitive:")30print("Search 'BANANA':", search_case_insensitive(fruits['apple', 'banana', 'cherry', 'date', 'elderberry'], "BANANA"))31print("Search 'Apple':", search_case_insensitive(fruits['apple', 'banana', 'cherry', 'date', 'elderberry'], "Apple"))
    outputSearch 'BANANA': 1

  13. target_lower ← apple

    pass 2 of 2
    12def search_case_insensitive(arr['apple', 'banana', 'cherry', 'date', 'elderberry'], targetApple):13    """Search ignoring case"""14    # Case-insensitive search15    target_lower→ apple = targetApple.lower()16    for i in range(len(arr)):

  14. if arr[i].lower() == target_lower:

    pass 2 of 2
    16for i in range(len(arr)):17    if arr[i]apple.lower() == target_lowerapple:18        return i019return -1

  15. print("Search 'Apple':", search_case_insensitive(fruits, "Apple"))

    30print("Search 'BANANA':", search_case_insensitive(fruits, "BANANA"))31print("Search 'Apple':", search_case_insensitive(fruits['apple', 'banana', 'cherry', 'date', 'elderberry'], "Apple"))
    outputSearch 'Apple': 0

Find All Occurrences

find_all.py
Replay: real traced execution (multi-file project)
# 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))

  1. numbers ← [3, 7, 3, 9, 3, 1, 3]

    16# Test finding multiple occurrences17numbers→ [3, 7, 3, 9, 3, 1, 3] = [3, 7, 3, 9, 3, 1, 3]1819print("List:", numbers[3, 7, 3, 9, 3, 1, 3])20print("All 3's at:", find_all(numbers[3, 7, 3, 9, 3, 1, 3], 3))21print("All 9's at:", find_all(numbers, 9))
    outputList: [3, 7, 3, 9, 3, 1, 3]

  2. indices ← []

    pass 1 of 3
    4def find_all(arr[3, 7, 3, 9, 3, 1, 3], target3):5    """Return list of all indices where target appears"""6    indices→ [] = []
    All 3 passes — pass 1 is the card above
    passtargetindices
    13[]
    29[]
    35[]

  3. for i in range(len(arr)):

    pass 1 of 21
    8# Collect all matching indices9for i0 in range(len(arr[3, 7, 3, 9, 3, 1, 3])):10    if arr[i] == target:11        indices.append(i)
    21 passes — pass 1 is the card above
    passi
    10
    21
    32
    43
    54
    65
    76
    80
    91
    ⋯ 10 more passes ⋯
    205
    216

  4. indices ← [0]

    pass 1 of 5
    9for i in range(len(arr)):10    if arr[i]3 == target3:11        indices→ [0].append(i0)
    All 5 passes — pass 1 is the card above
    passarr[i]targetiindices
    1330[] → [0]
    2332[0] → [0, 2]
    3334[0, 2] → [0, 2, 4]
    4336[0, 2, 4] → [0, 2, 4, 6]
    5993[] → [3]

  5. return indices

    13return indices[0, 2, 4, 6]

  6. print("All 3's at:", find_all(numbers, 3))

    19print("List:", numbers)20print("All 3's at:", find_all(numbers[3, 7, 3, 9, 3, 1, 3], 3))21print("All 9's at:", find_all(numbers[3, 7, 3, 9, 3, 1, 3], 9))22print("All 5's at:", find_all(numbers, 5))
    outputAll 3's at: [0, 2, 4, 6]

  7. return indices

    13return indices[3]

  8. print("All 9's at:", find_all(numbers, 9))

    20print("All 3's at:", find_all(numbers, 3))21print("All 9's at:", find_all(numbers[3, 7, 3, 9, 3, 1, 3], 9))22print("All 5's at:", find_all(numbers[3, 7, 3, 9, 3, 1, 3], 5))
    outputAll 9's at: [3]

  9. return indices

    13return indices[]

  10. print("All 5's at:", find_all(numbers, 5))

    21print("All 9's at:", find_all(numbers, 9))22print("All 5's at:", find_all(numbers[3, 7, 3, 9, 3, 1, 3], 5))
    outputAll 5's at: []
find_all Return all indices where the target appears, not just the first

Count Occurrences

count.py
Replay: real traced execution (multi-file project)
# 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}")

  1. numbers ← [10, 20, 30, 40, 50]

    17# Test with different positions18numbers→ [10, 20, 30, 40, 50] = [10, 20, 30, 40, 50]1920idx1, comp1 = linear_search_counted(numbers[10, 20, 30, 40, 50], 10)  # first element21print(f"Search 10: index={idx1}, comparisons={comp1}")

  2. comparisons ← 0

    pass 1 of 3
    4def linear_search_counted(arr[10, 20, 30, 40, 50], target10):5    """Return (index, comparisons) tuple"""6    comparisons→ 0 = 0
    All 3 passes — pass 1 is the card above
    passtargetarr[i]icomparisons
    1101000
    2505040
    399——0

  3. comparisons ← 1

    pass 1 of 11
    8# Count each comparison9for i0 in range(len(arr[10, 20, 30, 40, 50])):10    comparisons→ 1 += 111    if arr[i] == target:
    All 11 passes — pass 1 is the card above
    passiarr[i]targetcomparisons
    1010100 → 1
    20——0 → 1
    31——1 → 2
    42——2 → 3
    53——3 → 4
    6450504 → 5
    70——0 → 1
    81——1 → 2
    92——2 → 3
    103——3 → 4
    114——4 → 5

  4. if arr[i] == target:

    pass 1 of 2
    10comparisons += 111if arr[i]10 == target10:12    return (i0, comparisons1)

  5. idx1 ← 0, comp1 ← 1

    20idx1→ 0, comp1→ 1 = linear_search_counted(numbers[10, 20, 30, 40, 50], 10)  # first element21print(f"Search 10: index={idx10}, comparisons={comp11}")2223idx2, comp2 = linear_search_counted(numbers[10, 20, 30, 40, 50], 50)  # last element24print(f"Search 50: index={idx2}, comparisons={comp2}")
    outputSearch 10: index=0, comparisons=1

  6. if arr[i] == target:

    pass 2 of 2
    10comparisons += 111if arr[i]50 == target50:12    return (i4, comparisons5)

  7. idx2 ← 4, comp2 ← 5

    23idx2→ 4, comp2→ 5 = linear_search_counted(numbers[10, 20, 30, 40, 50], 50)  # last element24print(f"Search 50: index={idx24}, comparisons={comp25}")2526idx3, comp3 = linear_search_counted(numbers[10, 20, 30, 40, 50], 99)  # not found27print(f"Search 99: index={idx3}, comparisons={comp3}")
    outputSearch 50: index=4, comparisons=5

  8. return (-1, comparisons)

    14return (-1, comparisons5)

  9. idx3 ← -1, comp3 ← 5

    26idx3→ -1, comp3→ 5 = linear_search_counted(numbers[10, 20, 30, 40, 50], 99)  # not found27print(f"Search 99: index={idx3-1}, comparisons={comp35}")
    outputSearch 99: index=-1, comparisons=5

Predicate Search

predicate.py
Replay: real traced execution (multi-file project)
# 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)

  1. numbers ← [3, 7, 12, 5, 18, 9]

    13# Test with different conditions14numbers→ [3, 7, 12, 5, 18, 9] = [3, 7, 12, 5, 18, 9]1516print("List:", numbers[3, 7, 12, 5, 18, 9])1718# Find first even number19even_idx = find_first(numbers[3, 7, 12, 5, 18, 9], lambda x: x % 2 == 0)20print("First even at index:", even_idx)
    outputList: [3, 7, 12, 5, 18, 9]

  2. def find_first(arr, condition):

    pass 1 of 3
    4def find_first(arr[3, 7, 12, 5, 18, 9], condition<function <lambda> at ⟨addr A⟩>):5    """Find first element matching condition function"""6    # Search for first element matching condition
    All 3 passes — pass 1 is the card above
    passarr[i]i
    1122
    2122
    3——

  3. for i in range(len(arr)):

    pass 1 of 12
    6# Search for first element matching condition7for i0 in range(len(arr[3, 7, 12, 5, 18, 9])):8    if condition(arr[i]):9        return i
    All 12 passes — pass 1 is the card above
    passiarr[i]
    10—
    21—
    3212
    40—
    51—
    6212
    70—
    81—
    92—
    103—
    114—
    125—

  4. if condition(arr[i]):

    pass 1 of 2
    7for i in range(len(arr)):8    if condition(arr[i]12):9        return i210return -1

  5. even_idx ← 2

    18# Find first even number19even_idx→ 2 = find_first(numbers[3, 7, 12, 5, 18, 9], lambda x: x % 2 == 0)20print("First even at index:", even_idx2)2122# Find first number > 1023large_idx = find_first(numbers[3, 7, 12, 5, 18, 9], lambda x: x > 10)24print("First > 10 at index:", large_idx)
    outputFirst even at index: 2

  6. if condition(arr[i]):

    pass 2 of 2
    7for i in range(len(arr)):8    if condition(arr[i]12):9        return i210return -1

  7. large_idx ← 2

    22# Find first number > 1023large_idx→ 2 = find_first(numbers[3, 7, 12, 5, 18, 9], lambda x: x > 10)24print("First > 10 at index:", large_idx2)2526# Find first negative (not found)27neg_idx = find_first(numbers[3, 7, 12, 5, 18, 9], lambda x: x < 0)28print("First negative at index:", neg_idx)
    outputFirst > 10 at index: 2

  8. return -1

    9        return i10return -1

  9. neg_idx ← -1

    26# Find first negative (not found)27neg_idx→ -1 = find_first(numbers[3, 7, 12, 5, 18, 9], lambda x: x < 0)28print("First negative at index:", neg_idx-1)
    outputFirst negative at index: -1
predicate_search Search using a condition function instead of a specific value

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
time_complexity O(n) - must potentially check every element in the worst case

When to Use

  • Small lists
  • Unsorted data
  • Single search operation
  • When simplicity matters more than speed

Exercise: practical.py

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