Section 13.2 Sequential Search
The sequential search algorithm, also known as linear search, is a simple and straightforward algorithm used to locate a target value within a collection or array. It involves checking each element in the data structure one by one, sequentially, until the desired element is found or until all elements have been checked. This algorithm is often used when the data is not sorted, and its simplicity makes it easy to understand and implement.
The sequential search algorithm works as follows.
- Input: The algorithm takes two inputs: the target value that you want to find and the collection or array in which you’re searching for the target value.
- Initialization: Start at the first element (index 0) of the sequence.
-
Comparison: Compare the current element with the target value.
- If the current element is equal to the target value, the search is successful, and you’ve found the target value. The algorithm terminates.
- If the current element is not equal to the target value, move to the next element in the sequence.
- Repeat: Repeat steps 3 and 4 until the target value is found or until all elements in the sequence have been checked.
-
Termination:
- If the target value is found, the algorithm returns the index of the element where the target value was found.
- If the target value is not found after checking all elements, the algorithm indicates that the target value is not present in the sequence.
The time complexity of the sequential search algorithm is \(O(N)\text{,}\) where \(N\) is the number of elements in the data structure. In the worst case, the algorithm might have to examine every element to determine whether the target value is present or not. If the elements are in sorted order a better search algorithm may be binary search, which has better worst-case time complexities for large sequences.
While the sequential search algorithm is not the most efficient algorithm for searching in large sequential data structures, it is easy to understand and implement and can be useful for small sequences or when the data structure is unsorted. Sequential search may be the only option available.
In Listing 13.2.1, the
sequentialSearch(…) function takes an array (arr) and a target value (target) as parameters and searches for the target value within the array using the sequential search algorithm. The main method demonstrates how to use the sequential search function on an array.The sequential search algorithm iterates through the array elements one by one, comparing each element with the target value until the target is found or until all elements are checked. If the target is found, the function returns the index where the target was found. If the target is not found, the function returns -1, an impossible index.
// SequentialSearch.java
public class SequentialSearch {
// Sequential search function
static int sequentialSearch(int[] arr, int target) {
int n = arr.length;
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i; // Target found, return the index
}
}
return -1; // Target not found
}
public static void main(String[] args) {
int[] arrayToSearch = { 4, 2, 8, 5, 1, 9 };
int target = 5;
int result = sequentialSearch(arrayToSearch, target);
if (result != -1) {
System.out.println("Target " + target + " found at index " + result);
} else {
System.out.println("Target " + target + " not found in the array.");
}
}
}
SequentialSearch.javajavac SequentialSearch.java java SequentialSearch Target 5 found at index 3
