Linear search, also known as sequential search, is a simple searching algorithm that checks each element of a list in order until a match is found or the entire list has been traversed.

Algorithm Steps

1. Start at the beginning of the list.

1. Compare the target value with the current element.

1. If the target value matches the current element, the search is successful and the position of the element is returned.

1. If the target value does not match the current element, move to the next element in the list.

1. Repeat steps 2-4 until a match is found or the end of the list is reached.

Time complexity - O(n)

Because linear search potentially needs to check each item (n) in the list once in the list, the time complexity is O(n)

Space complexity O(1)

The space complexity of a linear search algorithm is generally O(1), which means it uses a constant amount of additional memory regardless of the size of the input data. This is because a linear search does not require any additional data structures or memory allocation that scales with the size of the input.

You may use a few variables for control and temporary storage, but the memory usage remains constant and doesn't depend on the size of the input data.

Advantages

• Simple and easy to understand
• Works on both sorted and unsorted lists
• Works well for small data sets
  
• Useful if you expect the item to be near the beginning of the list

Disadvantages

• Inefficient for large data sets
• Time complexity: O(n), where n is the size of the list
• Can be slow compared to other search algorithms

If the list is sorted, a linear search can stop early as soon as it passes the place where the target would be.

• Stop if the current item equals the target: found.
• Stop if the current item is greater than the target: the target is not in the list.

List: 3, 8, 12, 19, 25     Target: 10
3  < 10  → keep going
8  < 10  → keep going
12 > 10  → stop, not found

Only three items were checked instead of five. The worst case, a target larger than every item, still checks them all, so it is still O(n).

This function returns the index of the target, or -1 if it is not found. The elif branch adds the early exit for a sorted list.

def linear_search_sorted(items, target):
    for i in range(len(items)):
        if items[i] == target:
            return i          # found: stop early
        elif items[i] > target:
            return -1         # gone past it: stop early
    return -1                 # reached the end

numbers = [3, 8, 12, 19, 25]
print(linear_search_sorted(numbers, 19))
print(linear_search_sorted(numbers, 10))

3
-1

Without the elif branch, the same function works on an unsorted list, stopping early only when the target is found.