Python Linear Search

Python Linear Search

Linear Search, also known as sequential search, is the most straightforward searching algorithm. It sequentially checks each element of a list until a match is found or the whole list has been searched.

It's simple to understand and implement, but it's not the most efficient algorithm for large datasets.

How Linear Search Works

The algorithm follows these simple steps:

1. Start from the first element of the list.
2. Compare the current element with the target value you are searching for.
3. If the element matches the target, return the index of the element.
4. If the element does not match, move to the next element in the list.
5. Repeat steps 2-4 until the end of the list is reached.
6. If the target value is not found after checking all elements, return a value indicating that the element is not in the list (e.g., -1).

Implementing Linear Search in Python

Here is a simple function that implements the linear search algorithm.

def linear_search(data, target):
    """
    Searches for a target value in a list.
    Returns the index of the target if found, otherwise returns -1.
    """
    for i in range(len(data)):
        if data[i] == target:
            return i  # Target found, return its index
    return -1 # Target not found

// --- Usage ---
my_list = [10, 23, 45, 70, 11, 15]
target_value = 70
result = linear_search(my_list, target_value)
if result != -1:
    print(f"Element {target_value} is present at index {result}")
else:
    print(f"Element {target_value} is not present in the list")

Time Complexity

The performance of linear search is directly proportional to the number of elements in the list.

• Best Case: O(1) - The target is the very first element.
• Worst Case: O(n) - The target is the last element, or not in the list at all.
• Average Case: O(n) - On average, the algorithm will have to check half of the elements.

Because of its O(n) complexity, linear search is not suitable for large lists. For sorted lists, Binary Search is a much more efficient alternative.