Linear search, also known as sequential search, is a basic and straightforward searching algorithm used to find a specific element within a list or array of data. It works by sequentially checking each element in the list or array until a match is found or until all elements have been examined.
Here’s a step-by-step explanation of how a linear search works:
- Start at the beginning of the list or array.
- Compare the target element (the element you want to find) with the current element at the current position.
- If the current element matches the target element, the search is successful, and the index or position of the matching element is returned.
- If the current element does not match the target element, move to the next element in the list or array.
- Repeat steps 2-4 until a match is found or until you have checked all elements in the list.
- If the search reaches the end of the list without finding a match, it indicates that the target element is not present in the list, and the search returns a special value (such as -1) to indicate that the element was not found.
Example of linear search
Suppose we have the following list of elements [12, 5, 8, 3, 19, 7, 22] and we want to search for the target element 19 using a linear search. Here’s how the search process would look step by step:
Start at the first element (12) and compare it to the target (19).
[12] 5 8 3 19 7 22 {No match}
Move to the next element (5) and compare it to the target (19).
12 [5] 8 3 19 7 22 {No match}
Continue this process, moving through the list, one element at a time:
12 5 [8] 3 19 7 22
12 5 8 [3] 19 7 22
12 5 8 3 [19] 7 22 {Match found at index 4}
Since we found the target element 19 at index 4, we can stop searching and return the index where the match occurred.
In this graphical representation, the target element 19 was found in the list at index 4. Linear search proceeds sequentially through each element, and if it finds a match, it stops and reports the index. If the target element is not in the list, the search would continue until the end of the list, and the result would be -1 to indicate that the element was not found.
Python implementation
Here’s a simple example of a linear search implemented in Python. In this example, we’ll write a function that performs a linear search to find a target element in a list:
# Example usage:
my_list = [2, 4, 6, 8, 10, 12, 14]
target_element = 8
result = linear_search(my_list, target_element)
if result != -1:
print(f”{target_element} found at index {result}”)
else:
print(f”{target_element} not found in the list.”)
Linear search is straightforward and easy to implement, but it is not the most efficient searching algorithm for large datasets. Its time complexity is O(n), where n is the number of elements in the list or array. This means that in the worst-case scenario, you may have to check every element in the list to determine if the target element is present.
For large datasets or when efficiency is crucial, more advanced searching algorithms like binary search or hash tables are often used, as they offer faster average-case and worst-case time complexities for finding elements.
Expertvision 