Linear search algorithm is a simple and straightforward search algorithm that is used to find a specific element in a list or array. It is also known as a sequential search algorithm, which sequentially checks each element of the list until it finds the desired element.
How Linear Search Algorithm Works
Linear search algorithm works by iterating through each element of the list or array, starting from the first element, until it finds the desired element. If the desired element is found, the algorithm returns the index of that element in the list. If the desired element is not found, the algorithm returns a -1 to indicate that the element is not present in the list.
Python Implementation of Linear Search Algorithm
Here’s an example of implementing the linear search algorithm in Python:
def linear_search(arr, x): for i in range(len(arr)): if arr[i] == x: return i return -1
In the above code, the
linear_search function takes two arguments,
arr is the list or array to be searched, and
x is the element to be searched for. The function iterates through each element of the list using a
for loop and checks if the current element is equal to the element being searched for. If a match is found, the function returns the index of that element. If no match is found, the function returns -1.
Example of Linear Search Algorithm
Let’s say we have a list of numbers as follows:
arr = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
We want to search for the element 50 in this list using the linear search algorithm. We can do this by calling the
linear_search function with the list
arr and the element
50 as arguments:
index = linear_search(arr, 50)
After executing this code, the variable
index will contain the value
4, which is the index of the element
50 in the list.
Advantages and Disadvantages of Linear Search Algorithm
The linear search algorithm has the following advantages and disadvantages:
- Easy to understand and implement.
- Works well for small datasets.
- Inefficient for large datasets.
- Time complexity is O(n) where n is the number of elements in the list or array.
In conclusion, linear search algorithm is a simple and straightforward search algorithm that can be used to find a specific element in a list or array. Although it has some limitations, it is still useful for small datasets or when the list is not sorted.
- What is the time complexity of linear search algorithm?
- The time complexity of linear search algorithm is O(n), where n is the number of elements in the list or array.
- What is the difference between linear search and binary search?
- Linear search checks each element of the list sequentially until it finds the desired element, while binary search divides the list into halves and checks the middle element.
- What is the best use case for linear search algorithm?
- Linear search algorithm is best used for small datasets or when the list is not sorted.
- Can linear search be used on a sorted list?
- Yes, linear search can be used on a sorted list, but it is not efficient compared to binary search.
- Is linear search algorithm recursive?
- No, linear search algorithm is not recursive. It uses a simple iterative approach to search for an element in a list or array.
For complete list of topic on DATA STRUCTURE AND ALGORITHM click hear