Linear Search Algorithm

In programming, there are many ways in which to find an element in a given data structure, such as an array or list. For simplicity, we will use an array in the examples in this article. The easiest search algorithms are what we refer to as a linear or sequential searches. As the name indicates, these algorithms look at the elements sequentially, or one after another, in the order in which they appear in the data structure. Such algorithms can be implemented in several ways such as by using foreach, while or for loops.

Below I give you examples of how to find an element in an array with the before mentioned approaches. We will return true if the element exists, but it is also common to return the index of the element (-1 if not found). The examples are written in PHP, but the syntax is very straightforward, even if you are not familiar with the language. Rewriting the examples to work in languages such as Java or C# is very simple.

function find1(array $myArray, $elementToFind) {
	foreach ($myArray as $element) {
		if ($element === $elementToFind) {
			return true;
		}
		
		return false;
	}
}

In the example above, we have implemented the algorithm by using a foreach loop. As the name of the loop implies, all elements in our data collection are looped through – unless we specify otherwise, that is. In this case, we are returning true if the current element is the one we are looking for, which terminates the loop immediately and ignores any remaining code in the function. Each element in the array is referenced as $element within the scope of the foreach loop (within the curly brackets, except for the last iteration). This variable will reference elements at different indexes for every iteration, in the order in which elements appear in the array. If the element does not exist in the array, the loop is terminated after checking all of the elements, and then false is returned as per the last statement.

function find2(array $myArray, $elementToFind) {
	$i = 0;
	$count = count($myArray);

	while ($i < $count) {
		if ($myArray[$i] === $elementToFind) {
			return true;
		}
				
		$i++;
	}
		
	return false;
}

In the above example, we use the while loop to accomplish our task. This kind of loop will continue executing the code within the curly brackets while the condition in parenthesis is true. Once the condition evaluates to false, the loop terminates. However, the loop does not terminate immediately, but only after the code within the curly brackets has been executed. This is because the specified loop condition is evaluated before each iteration of the loop.

With this approach, we are using an index counter $i to iterate through the array, hence why we check the element at position $i in $myArray instead of $element as in the previous example. We could assign the current element to a variable and then use it in our if statement if we wanted; to some, this is more readable, but it also adds an additional instruction to our algorithm. However, the latter is of little importance performance wise as we shall see later in this article. Here we keep looping while $i is less than the count of elements in the array, because if the function has not returned yet, then we should check more elements. We are using the less than operator and not less than or equal to because indexes start from zero and not one, which most people would find logical at first.

function find3(array $myArray, $elementToFind) {
	$count = count($myArray);

	for ($i = 0; $i < $count; $i++) {
		if ($myArray[$i] === $elementToFind) {
			return true;
		}
	}
		
	return false;
}

For the last example, we have used the for loop, which consists of initialization, a loop condition and a statement to be executed after each iteration. These expressions are separated by semicolons. Usually a for loop will be of the form as seen in our example, but the for loop is in fact quite flexible. The expressions can be empty and can even contain several expressions. For more information about the for loop, we refer you to the PHP documentation. As you might have noticed, this approach looks much like the second example with the while loop. First we initialize the variable $i to 0 and increment it by one after each iteration. The loop condition is checked before each iteration. Like with the while loop, it is this condition that determines if and when the loop should terminate. The rest of the algorithm is the same as we saw in the previous example.

Please note that there are many variations of these linear or sequential search algorithms, but the main concept is the same.

Efficiency

One thing these algorithms have in common is that they are often very inefficient. They are certainly effective for small data collections, but the amount of data usually grows with time. Furthermore, such an algorithm can be used in many different scenarios, hence why it can be very hard to predict how much data the algorithm will handle ahead of time.

What if the element we are searching for is the last element in the list? In this case, we would have to search through all of the other elements before finally reaching the element we are looking for (because we cannot know that the element is the last one). This may not be a problem if we are to search through 10 or 50 elements, but it is an entirely different story if the number is five million. On average, we would have to search through 2.5 million elements every time, with a worst case scenario of all five million. As you might suspect, this is not efficient.

In the Big O notation, the efficiency of this type of algorithm belongs to the linear class, which is noted as O(n).

Luckily there are measures to improve performance, most noticeably by using a binary search algorithm. Such an algorithm does, however, require that the data collection is sorted, which is not without cost. These algorithms are furthermore slightly more complicated to implement, but the performance gain can be drastic. This type of algorithm belongs to the logarithmic class in the Big O notation; O(log n).