Computer Science – 19.1 Algorithms | e-Consult

Linear Search:

Linear search is a simple algorithm that sequentially checks each element in a list until the target value is found or the entire list has been traversed.

Steps:

• Start at the beginning of the list.
• Compare the current element with the target value.
• If the current element matches the target value, the search is successful.
• If the current element does not match the target value, move to the next element in the list.
• Repeat step 2 and 3 until the target value is found or the end of the list is reached.
• If the end of the list is reached without finding the target value, the search is unsuccessful.

Time Complexity:

• Best Case: O(1) - The target value is the first element in the list.
• Worst Case: O(n) - The target value is the last element in the list or is not present.
• Average Case: O(n) - On average, the algorithm will need to examine half of the elements in the list.

Comparison with Binary Search:

Binary search requires the list to be sorted. Linear search does not have this requirement. Binary search has a time complexity of O(log n), which is significantly faster than linear search's O(n) for large lists. However, the overhead of maintaining a sorted list can make binary search less efficient for small lists. Linear search is simpler to implement but less efficient for large datasets. Binary search is preferred when the data is sorted and performance is critical.