Searching: Basic Search Techniques: Sequential Search

Definition

Sequential search is a search algorithm in which each element of a list, array, or sequence is examined in order from the beginning to the end until the required element is found or the entire collection has been checked.

Main Content

1. Sequential Search in an Unsorted List

• In an unsorted list, sequential search starts from the first element and compares it with the target value.
• The process continues element by element until a match is found or the list is exhausted, making it suitable for data that has not been arranged in any particular order.

Example:
If the list is 45, 12, 89, 33, 27 and the target is 33, the search checks 45, then 12, then 89, and finally 33.

2. Sequential Search in a Sorted List

• Sequential search can also be applied to sorted lists, although it is not the most efficient method for them.
• A small optimization may be used: if the list is sorted in ascending order and the current element becomes greater than the target, the search can stop early because the target cannot appear later.

Example:
If the list is 10, 20, 30, 40, 50 and the target is 25, the search checks 10, 20, and then stops at 30 because 30 > 25.

3. Performance and Characteristics of Sequential Search

• The best-case time occurs when the target is found at the first position, giving very fast results.
• The worst-case time occurs when the target is at the last position or not present at all, requiring every element to be checked.

Time complexity:

• Best case: O(1)
• Average case: O(n)
• Worst case: O(n)

Space complexity:

• O(1) because only a small number of variables are needed.

Working / Process

1. Start from the first element of the list or array.
2. Compare the current element with the target value.
3. If the element matches the target, stop and return the position; otherwise, move to the next element and repeat until the end of the collection.

Example process for target 33 in 15, 22, 9, 33, 41:

15 → compare
22 → compare
9 → compare
33 → match found

For a clearer visual understanding of how the search moves through elements, consider the following representation:

[15] -> [22] -> [9] -> [33] -> [41]
↑
                   target found here

Advantages / Applications

• It is very easy to understand and implement, making it ideal for beginners and basic programming tasks.
• It works on both sorted and unsorted data, so it is useful in many practical situations where no ordering is guaranteed.
• It requires no additional memory and is suitable for small datasets, linked lists, and simple database-style lookups.

Summary

• Sequential search checks elements one by one until the target is found.
• It is simple and works well for small or unsorted data.
• It may be slow for large lists because many comparisons can be needed.
• Important terms to remember: sequential search, linear search, target element, comparison, time complexity, unsorted list.