- Linear search is a simple searching algorithm that iterates through an array or list to find a specific element. It checks each element one by one until a match is found or the entire list is traversed.
Key Characteristics Of The Linear Search Algorithm Include
- Sequential Examination: It examines each element in the list one by one, starting from the beginning until the desired element is found or the end of the list is reached.
- Unordered List Handling: Linear search can be used on both ordered and unordered lists, making it versatile for various types of datasets.
- Simplicity: The algorithm is easy to understand and implement, making it a common choice for small datasets and situations where a more complex algorithm might be unnecessary.
- Time Complexity: Linear search has a time complexity of O(n), where n is the number of elements in the list. This means that the time taken to search increases linearly with the size of the list.
Algorithm
Linear_Search(a, n, val)
// 'a' is the given array, 'n' is the size of given
array, 'val' is the value to search
Step 1: set pos = -1
Step 2: set i = 1
Step 3: repeat step 4 while i <= n
Step 4: if a[i] == val
set pos = i
print pos
go to step 6
[end of if]
set ii = i + 1
[end of loop]
Step 5: if pos = -1
print "value is not present in the array "
[end of if]
Step 6: exit
Working of Linear Search
Linear search is a straightforward searching algorithm that sequentially checks each element of the list until it finds the target value or reaches the end of the list. Here is how the linear search algorithm works:
- Step 1: Start from the first element of the list.
- Step 2: Compare the current element with the target value.
- Step 3: If the current element matches the target value, the search is successful, and the index of the element is returned.
- Step 4: If the current element does not match the target value, move to the next element in the list and repeat Step 2.
- Step 5: Continue this process until the target value is found, or until all elements in the list have been checked.
- Step 6: If the target value is not found after checking all elements, the search is unsuccessful, and the algorithm returns a special value, such as -1, to indicate that the target value is not present in the list.
Linear Search Complexity
Time Complexity:
| Case | Time Complexity |
|---|---|
| Best Case | O(1) |
| Average Case | O(n) |
| Worst Case | O(n) |
- Best Case Complexity – In Linear search, best case occurs when the element we are finding is at the first position of the array. The best-case time complexity of linear search is O(1).
- Average Case Complexity – The average case time complexity of linear search is O(n).
- Worst Case Complexity – In Linear search, the worst case occurs when the element we are looking is present at the end of the array. The worst-case in linear search could be when the target element is not present in the given array, and we have to traverse the entire array. The worst-case time complexity of linear search is O(n).
