Search algorithms

When searching for a value in a data structure, there are different approaches we can take. Let’s take a look at two of the most used options and compare them.

Linear search

Linear search consists in iterating over the data structure one value at a time and checking if that value is the one we’re looking for. It’s probably the most intuitive kind of search and the best we can do is the data structure we’re using isn’t ordered.

Let’s say we have an array of numbers.

And for this array we want to write a function that takes a number as the input and returns that number’s index in the array. In case it doesn’t exist in the array It will return -1. A possible approach could be the following:

A simple loop that iterates over the array one value at a time, and returns the value’s index if it’s the same as the input number.

As the array isn’t ordered, we don’t have a way of knowing the approximate position of each value, so the best we can do is check one value at a time. The complexity of this algorithm is linear (O(n)) since in the worst case scenario we will have to iterate over the whole array once to get the value we’re looking for.

Linear search is the approach used by many built-in javascript methods like indexOf, includes and findIndex.

Binary search

When we have an ordered data structure, there’s a much more efficient approach we can take. What we do in binary search is the following:

• Select the middle value of our data structure and “ask”, is this the value we’re looking for?
• If not we “ask”, is the value we’re looking for greater or less than the middle value?
• If it’s greater, we “discard” all the values lesser than the mid value. If it’s less, we “discard” all the values greater than the mid value. And then we repeat the same operation.

Let’s say we have an ordered array this time.

And we want to write the same function than before, which takes a number as the input and returns that number’s index in the array. In case it doesn’t exist in the array It will return -1. A binary search approach could be the following:

We start by defining a start variable at 0, an end variable at the last index of the array, and a middle variable calculated by dividing the start plus the end variables by two.

Then we start a loop that will last until the middle value is different to the number we’re looking for and the start is less or equal to the end.

Within the loop, we check if the number we’re looking for is less than the middle value, and if it is we change the end value to middle-1, hence discarding all the greater values than middle and “chopping” our data structure in half. We do the opposite if the number is greater than the middle value, changing the start value and discarding all lesser values. Last, we recalculate our middle value, and in case it still doesn’t match our desired value, we go through the loop again.

Once we divided the array all the times we could (we check this with the start <= end condition) if the middle value isn’t the number we’re looking for, the function returns -1.

This approach may seem like “more code” at first, but potential iterations are actually a lot less than in linear search, and that’s because in each iteration we’re discarding half of the data structure. The complexity of this algorithm is logarithmic (O(log n)).