Linear Search: Implement the linear search in python to find an element in an unsorted list.
Introduction Searching is a fundamental problem in computer science and various algorithms are available to solve this problem. One of the simplest and easiest to implement algorithms is linear search. Linear search also known as sequential search is used to find an element in an unsorted list or array. In this blog post we will discuss the linear search algorithm and its implementation in Python.
3 Ways to Implement Binary Search in Python
Linear Search in Python
Linear Search Algorithm Linear search is a simple searching algorithm that works by sequentially checking each element in a list or array until the target element is found. The algorithm compares the target element with each element in the list until a match is found or the end of the list is reached. If the target element is found the algorithm returns the index of the element otherwise it returns -1 to indicate that the element is not present in the list.
Here is the step-by-step algorithm for linear search in python:
- Start at the beginning of the list.
- Compare the target element with the current element in the list.
- If the target element is found return the index of the element.
- If the end of the list is reached without finding the target element return -1.
Python Implementation The following is a Python implementation of the linear search algorithm
def linear_search(arr, target):
"""
Perform a linear search to find the target element in the array.
Return the index of the element if found, or -1 if not found.
"""
for i in range(len(arr)):
if arr[i] == target:
return i
return -1
The linear_search the function takes two arguments arr is the list to search for and target is the element to find. The function loops through each element in the list and compares it with the target element. If a match is found the function returns the index of the element otherwise it returns -1.
Testing the Function We can test the linear_search function with some sample data to confirm its correctness. Here are some test cases:
# Test case 1: element found in the middle of the list
arr = [3, 5, 7, 8, 4, 9, 1]
target = 8
result = linear_search(arr, target)
print(f"The index of {target} in the list is {result}.")
# Expected output: The index of 8 in the list is 3.
# Test case 2: element found at the beginning of the list
arr = [3, 5, 7, 8, 4, 9, 1]
target = 3
result = linear_search(arr, target)
print(f"The index of {target} in the list is {result}.")
# Expected output: The index of 3 in the list is 0.
# Test case 3: element not found in the list
arr = [3, 5, 7, 8, 4, 9, 1]
target = 6
result = linear_search(arr, target)
print(f"The index of {target} in the list is {result}.")
# Expected output: The index of 6 in the list is -1.
Output:
The index of 8 in the list is 3.
The index of 3 in the list is 0.
The index of 6 in the list is -1.
The output confirms that the linear_search the function works correctly and returns the index of the target element if it is found or -1 if it is not present in the list.