Linear Search

2022-11-27

Given an arbitrary sequence S with n elements, the problem of search is to find the position of a given element e in S or assert its absence.

If there is no additional information about the sequence S, there is no better approach than visiting every element of S, which might as well be done in sequence order.

Naturally, linear search has O(n) complexity, with respect to the number of elements n of S.

def linear_search(arr, e):
    for i in range(len(arr)):
        if arr[i] == e:
            return i
    return -1  # sentinel value for "not found"