Linear Search

Welcome to Data Structures and Algorithms with Python! In this course, we will be learning how to use Python to solve data structure and algorithm problems. This article will provide an in-depth look at the Linear Search Algorithm, including how it works, its time and space complexities, and examples of how to implement it in Python. At the end of the article, you will also find five coding exercises with solutions to help you test your understanding of the material.

What is Linear Search?

Linear search is an algorithm used to search for an element in a given list or array of elements. It is a simple algorithm that starts at the beginning of the list and traverses through each element until it finds a match or reaches the end of the list. Linear search can be used to search for a specific element in an array, or to find the index of an element in an array.

How Does Linear Search Work?

Linear search works by starting at the beginning of the list and checking each element in the list until it finds a match or reaches the end of the list. It does this by comparing each element in the list to the element we are searching for. If the element we are searching for is found, the Linear Search algorithm returns the index of the element in the array. If it is not found, the algorithm returns -1.

The following is an example of how the Linear Search algorithm works. Let’s say we have the following array:

arr = [1, 3, 4, 5, 6, 7, 8]

We want to search for the element 5. The Linear Search algorithm starts at the beginning of the list and checks each element in the list until it finds a match or reaches the end of the list. In this case, the algorithm finds 5 at index 3 and returns the index of the element (3).

Time Complexity

The time complexity of the Linear Search algorithm is O(n). This means that the time taken by the algorithm to search for an element increases linearly with the size of the list or array.

The best case time complexity of the Linear Search algorithm is O(1). This means that the time taken by the algorithm to search for an element is constant regardless of the size of the list or array. This happens when the element we are searching for is at the beginning of the list.

The worst case time complexity of the Linear Search algorithm is O(n). This means that the time taken by the algorithm to search for an element increases linearly with the size of the list or array. This happens when the element we are searching for is at the end of the list.

Space Complexity

The space complexity of the Linear Search algorithm is O(1). This means that the space taken by the algorithm to search for an element is constant regardless of the size of the list or array.

Python Implementation

Now that we have an understanding of how the Linear Search algorithm works and its time and space complexities, let’s look at how to implement it in Python.

The following is an example of how to implement the Linear Search algorithm in Python:

def linear_search(arr, target):
    # Set pointer to first element
    pointer = 0
    
    # Loop through array
    while pointer < len(arr):
        # Check if element is target value
        if arr[pointer] == target:
            # Return index if found
            return pointer
        # Move pointer to next element
        pointer += 1
    
    # Target value not found
    return -1

The code above is a basic implementation of linear search in Python. It takes in an array or list (arr) and a target value (target), and returns the index of the target value if it is found in the array. If the target value is not found, it will return -1.

Conclusion

In this article, we have discussed the Linear Search algorithm and looked at how it works, its time and space complexities, and how to implement it in Python. Linear search is a simple algorithm that can be used to search for an element in an array or to find the index of an element in an array. The time complexity of the Linear Search algorithm is O(n) and the space complexity is O(1).

Exercises

def linear_search(arr, target):
    # Set pointer to first element
    pointer = 0
    
    # Loop through array
    while pointer < len(arr):
        # Check if element is target value
        if arr[pointer] == target:
            # Return index if found
            return pointer
        # Move pointer to next element
        pointer += 1
    
    # Target value not found
    return -1

def linear_search(arr, target):
    # Set pointer to first element
    pointer = 0
    
    # Loop through array
    while pointer < len(arr):
        # Check if element is target value
        if arr[pointer] == target:
            # Return true if found
            return True
        # Move pointer to next element
        pointer += 1
    
    # Target value not found
    return False

def linear_search(arr, target, start_index):
    # Set pointer to start index
    pointer = start_index
    
    # Loop through array starting from start index
    while pointer < len(arr):
        # Check if element is target value
        if arr[pointer] == target:
            # Return index if found
            return pointer
        # Move pointer to next element
        pointer += 1
    
    # Target value not found
    return -1

def linear_search(arr, target):
    # Set pointer to last element
    pointer = len(arr) - 1
    
    # Loop through array in reverse
    while pointer >= 0:
        # Check if element is target value
        if arr[pointer] == target:
            # Return index if found
            return pointer
        # Move pointer to previous element
        pointer -= 1
    
    # Target value not found
    return -1

def linear_search(arr, target):
    # Set counter to 0
    counter = 0
    # Set pointer to first element
    pointer = 0
    
    # Loop through array
    while pointer < len(arr):
        # Check if element is target value
        if arr[pointer] == target:
            # Increment counter if found
            counter += 1
        # Move pointer to next element
        pointer += 1
    
    # Return counter
    return counter