Linear Search with Duplicates

Linear Search scans an array sequentially, comparing each element with the target value. When an array contains duplicate values, a simple linear search that returns on the first match may not be enough — often we need all indices where the value occurs.

Algorithm Steps

• Start from the first index of the array.
• Compare the current element with the target value.
• If it matches, record the index (instead of stopping).
• Continue until the end of the array is reached.
• Return the list of all matching indices.

def linear_search_all(arr, target):
    indices = []
    for i, value in enumerate(arr):
        if value == target:
            indices.append(i)
    return indices

print(linear_search_all([4, 2, 7, 2, 9, 2], 2))  # Output: [1, 3, 5]

Complexity

When to Use

• Unsorted arrays where binary search cannot be applied.
• Small datasets where the overhead of sorting is not worthwhile.
• Situations that require every occurrence of a value, not just existence.