How to Implement a Sequential Search Algorithm?
Searching an element in a list is an essential algorithm and understanding the different types of searching algorithms will help you build a well-designed application which can have good performance. In fact, there are different types of searching algorithms which are developed based on the data-structures (DS) such as Linear and Non-Linear. Linear DS require sequential search because “Data structure where data elements are arranged sequentially or linearly where the elements are attached to its previous and next adjacent in what is called a linear data structure.” (GFG). On the other hand, a non-linear DS require non-sequential algorithms because the list can’t be sequentially searched. A tree is a good example of non-linear DS. In this tutorial, we will implement a sequential search on an unordered list. Even though, sequential search can be used on a sorted list, but it is not efficient. If you do use sequential search on a sorted list, you can stop your search at the number greater than the target value. For example, if there are 10 elements in an array, and you are looking for number 4, if you reach number five without finding 4, then you can exit the loop because 5 is greater than 4 and in a sorted array 4 comes before 5.
Imagine that there are 100 people in a line. and you are asked to find a person named “John Doe.” Using sequential search, you will start from the first person and keep asking “What is your name?” until you find the person. In the worst-case scenario, you will end up walking to the end of the line without finding the person, or the last person can be the one you are looking for. If the person is standing at the beginning of the line, this is your best-case scenario because it didn’t exhaust you. However, if the person is the 99th or 100th in the line, then you have encountered the worst-case scenario because you exhausted yourself by asking every individual in the line about their identity. Furthermore, in the average-case, the person can be in the middle of the line. This search can as simple as finding one unique element in the array or can get a little complex by having many of identical elements. However, the search process itself is important, but the extra conditions can easily be added to the question the identity of the person that you are looking for. For instance, if you ask the first person “What is your name?” the reply could be “My name is Jon Doe?” now, you can add if-else condition to check for his attributes such as: “What is your ID? Is this person wearing a red shirt?” etc.…
Now, imagine if the line had a million (n = million) people standing and you are asked to find a unique person. If the person is located at the beginning of the line, not an issue, but we are always concerned with the worst-case scenario, therefore, if the person is located at n-1 (million-1), then it will take much more time to locate the person.
In the following figure, we want to find the number 6 in an array list. We start at the beginning of the line and loop through the list and keep asking does array of index 0…7 have the element 6? Once found then it returns “true”, otherwise, it returns “false.”
Let’s implement this in JavaScript.
Java implementation
Tester class
