Explain linear search algorithm
Linear search algorithm is a simple search algorithm used to find a target value within a list or an array of elements. It starts from the beginning of the list and sequentially moves through each element until either the target value is found or the end of the list is reached.
To perform a linear search, the algorithm compares each of the elements in the list with the target value. If a match is found, the algorithm returns the index position of that element. If no match is found after searching through all the elements, the algorithm returns a special value (often -1) to indicate that the target value is not present in the list.
The steps of the linear search algorithm are as follows:
1. Initialize a variable to store the position of the target value (initially set to -1).
2. Start from the first element of the list.
3. Compare the value of the current element with the target value.
4. If they are equal, store the index position of the current element and exit the loop.
5. If they are not equal, move to the next element.
6. Repeat steps 3 to 5 until the end of the list is reached or a match is found.
7. If a match is found, return the index position of the element. Otherwise, return the special value indicating that the target value is not present.
The linear search algorithm has a time complexity of O(n) in its worst-case scenario, where n is the number of elements in the list. This means that the time it takes to perform the search increases linearly with the size of the list. The algorithm is straightforward and easy to implement but may not be efficient for large lists or when performance is a critical factor.