Linear, Binary, and Interpolation Search Algorithms Explained

#javascript #webdev #beginners #algorithms

In my last post, I took a look at some of the most common sorting algorithms in JavaScript. Now, I'd like to talk about searching algorithms. If you've checked out some of my other posts, for example the one on binary search trees, then you'll notice that this isn't the first time I've written about searching algorithms on DEV. That being said, I'm aiming for this article to take a deeper look at some of the most common searching algorithms and really break them down. In this article, I'll cover the following searching algorithms:

Linear Search (aka Sequential Search)
Binary Search
Interpolation Search

Linear Search

Also known as the sequential search, the linear search is the most basic searching algorithm. With a big-O notation of O(n), the linear search consists of comparing each element of the data structure with the one you are searching for. It's up to your implementation whether you return the value you were looking for or a boolean according to whether or not the value was found. As you can probably guess, this is a very inefficient process.



function linearSearch(arr, target) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i] === target) return i;
    }
    return null;
}

Binary Search

The binary search algorithm works with a sorted data structure. In this implementation we will use the quicksort algorithm. The big-O notation for this algorithm is O(log n). The process looks something like this:

Select a value in the middle of the (sorted) array
If the value is what we are searching for, we are done
Otherwise, if what we are searching for is less than the value, go back to step one with the left subarray
Or, if what we are searching for is greater than the value, go back to step one with the right subarray



function binarySearch(arr, target) {
    const sortedArr = quickSort(arr);
    let low = 0;
    let high = sortedArr.length - 1;
    while (low <= high) {
        const mid = Math.floor(low + high);
        const element = sortedArr[mid];
        if (element < target) {
            low = mid + 1;
        } else if (element > target) {
            high = mid - 1;
        } else {
            return mid;
        }
    }
    return null;
}

Interpolation Search

The interpolation search is basically an improved version of the binary search. This searching algorithm resembles the method by which one might search a telephone book for a name: with each step, the algorithm calculates where in the remaining search space the target element might be based on the value of the bounds compared to the target element. If elements are uniformly distributed, the time complexity is O(log (log n)). In worst cases it can take up to O(n).

The steps to this algorithm are the same as the steps for binary search except for the first step. Instead of selected a value in the middle of the array as the value, we will select it using the position formula which you will notice in our implementation below:



function interpolationSearch(arr, target) {
    let low = 0;
    let high = arr.length - 1;
    let position = -1;
    let delta = -1;
    while (low <= high && target >= arr[low] && target <= arr[high]) {
        delta = (target - arr[low])/(arr[high] - arr[low]);
        position = low + Math.floor((high - low) * delta);
        if (arr[position] === target) {
            return position;
        }
        if (arr[position] < target) {
            low = position + 1;
        } else {
            high = position - 1;
        }
    }
    return null;
}

Note that in the following example, the distribution is very uniform and the delta/difference is very small, making this a pretty ideal situation for this search.

Conclusion

I hope that this article helped you gain a clearer understanding of some common search algorithms. Searching algorithms are fundamental to algorithm practice and open doors to much more complex and interesting solutions. Stay tuned as I hope to go over some interesting algorithms in future posts that will rely on much of the material covered in this post.