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
Write a function that takes in an array and a target value, and returns the index of the target value if it is found. If the target value is 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 index if found
return pointer
# Move pointer to next element
pointer += 1
# Target value not found
return -1
Write a function that takes in an array and a target value, and returns true if the target value is found in the array, and false if it is not.
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
Write a function that takes in an array, a target value, and a start index. The function should return the index of the target value if it is found starting from the given start index. If the target value is not found, the function should return -1.
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
Write a function that takes in an array and a target value, and returns the index of the last occurrence of the target value in the array. If the target value is not found, the function should 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
Write a function that takes in an array and a target value, and returns the number of times the target value appears in the array.
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