Linear Search using Python

 

Linear search is a simple search algorithm that involves examining each element of a list, one by one, from the beginning until the desired element is found or the end of the list is reached. Here is an example of how to implement linear search in Python:

def linear_search(list, target):
  # Iterate through the list
  for i in range(len(list)):
    # If the target is found, return the index
    if list[i] == target:
      return i
  # If the target is not found, return -1
  return -1

# Test the function with a sample list and target
list = [1, 2, 3, 4, 5]
target = 3
index = linear_search(list, target)
print(index)  # Output: 2

This implementation of linear search has a time complexity of O(n), meaning that the time it takes to run the search grows linearly with the size of the list. This makes it inefficient for large lists. For lists with a large number of elements, it is usually better to use a more efficient search algorithm such as binary search.

Using Recursion

def linear_search_recursive(list, target, index=0):
  # Base case: if the index is greater than or equal to the length of the list, the target is not present
  if index >= len(list):
    return -1
  # If the target is found, return the index
  if list[index] == target:
    return index
  # Otherwise, call the function again with an incremented index
  return linear_search_recursive(list, target, index+1)

# Test the function with a sample list and target
list = [1, 2, 3, 4, 5]
target = 3
index = linear_search_recursive(list, target)
print(index)  # Output: 2

This implementation of linear search using recursion has the same time complexity as the iterative version: O(n). It may be less efficient in practice due to the overhead of the recursive function calls.