Linear, Binary, and Interpolation Search Algorithms Explained
Tags: javascript, webdev, beginners, algorithms
Published: 2020-08-16 23:35:27

In my last post, I took a look at some of the most common [sorting algorithms](https://dev.to/christinamcmahon/common-sorting-algorithms-in-javascript-58a7) 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](https://dev.to/christinamcmahon/understanding-binary-search-trees-4d90), 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](https://dev.to/christinamcmahon/runtime-analysis-big-o-notation-906) 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. 

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

![linear search example](https://dev-to-uploads.s3.amazonaws.com/i/19k583f8kooery0sthod.png)

# 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:

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

```javascript
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;
}
```

![binary search example](https://dev-to-uploads.s3.amazonaws.com/i/y4p0iebdeervn1t8c6ca.png)

# 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:

```javascript
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.

![interpolation search example](https://dev-to-uploads.s3.amazonaws.com/i/hf7i14stmqz2gehtttyz.png)

# 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.