Linear Search in Python

by

Sure! Here’s an implementation of linear search in Python:

def linear_search(arr, x):
    """
    Searches for an element x in an array arr using linear search.
    
    Parameters:
    arr (list): The array to be searched.
    x (int): The element to be searched for.
    
    Returns:
    int: The index of the first occurrence of x in arr, or -1 if x is not found.
    """
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1

The function takes in two parameters, an array arr and an element x to search for. It then iterates through the array using a for loop, checking if each element is equal to x. If it finds a match, it returns the index of that element. If it reaches the end of the array without finding a match, it returns -1 to indicate that x was not found in arr.

What is a Linear Search?:

Linear search is a simple searching algorithm that scans an array of elements sequentially to find a specific value. It starts from the first element of the array and compares each element with the value being searched until a match is found or the end of the array is reached.

The time complexity of linear search is O(n), where n is the number of elements in the array. This means that the worst-case scenario for linear search is when the element being searched is at the end of the array, or when the element is not in the array at all, in which case it would have to scan through all n elements.

Although linear search is not the most efficient search algorithm, it can be useful for small arrays or for unsorted arrays. It is also easy to implement and understand.

Concept of Linear Search:

Linear search, also known as sequential search, is a basic algorithm used to find a specific element in an array or a list of elements. It works by sequentially checking each element of the array, starting from the first element, until the element being searched for is found or until the end of the array is reached.

The algorithm can be described as follows:

  1. Initialize a variable to keep track of the current position in the array.
  2. Compare the element at the current position with the element being searched for.
  3. If the two elements match, return the current position.
  4. If the two elements do not match, move to the next position in the array and repeat steps 2 and 3.
  5. If the end of the array is reached without finding a match, return a “not found” indication.

Linear search is a simple algorithm and is easy to understand and implement. However, its time complexity is O(n), where n is the number of elements in the array, which means that it can become inefficient for large arrays. Other search algorithms, such as binary search, can be more efficient for larger datasets.

Linear Search Algorithm:

Here’s the algorithm for Linear Search:

  1. Start with the first element of the array.
  2. Compare the first element with the target value.
  3. If the first element is equal to the target value, return its index and terminate the algorithm.
  4. If the first element is not equal to the target value, move to the next element in the array.
  5. Repeat steps 2-4 until the target value is found or until the end of the array is reached.
  6. If the target value is not found, return a “not found” indication.

The time complexity of Linear Search is O(n), where n is the number of elements in the array. The worst-case scenario occurs when the target value is not in the array or when it is at the end of the array, and the algorithm has to search through all n elements of the array.

Linear Search Complexity:

The time complexity of Linear Search is O(n), where n is the number of elements in the array.

This means that the worst-case scenario for linear search is when the target value is not in the array or when it is at the end of the array, and the algorithm has to search through all n elements of the array.

In the best-case scenario, the target value is found in the first element of the array, and the algorithm only needs to perform one comparison operation. In the average case, the target value is found in the middle of the array, and the algorithm needs to perform n/2 comparison operations.

However, Linear Search has a space complexity of O(1), which means that it only requires a constant amount of memory to run, regardless of the size of the input array. This is because the algorithm only needs to store a few variables to keep track of its progress through the array.