In this post, I’ll compare linear search and binary search algorithms. You’ll learn pseudocode for linear and binary algorithms, see examples to demonstrate both the methods, learn about time complexity, and get a step-by-step guide on how to implement the algorithms.

## Introduction

As a programmer, you want to find the best solution to a problem so that your code is not only correct but also efficient. Choosing a suboptimal algorithm could mean a longer completion time, increased code complexity, or worse, a program that crashes.

You may have used a search algorithm to locate items in a collection of data. The JavaScript language has several methods, like `find`

, to locate items in an array. However, these methods use linear search. A linear search algorithm starts at the beginning of a list and compares each element with the search value until it is found.

This is fine when you have a small number of elements. But when you are searching large lists that have thousands or millions of elements, you need a better way to locate items. This is when you would use binary search.

In this tutorial, I will explain how binary search works and how to implement the algorithm in JavaScript. First, we will review the linear search algorithm.

## Linear Search

We will begin by explaining how to implement linear search in JavaScript. We will create a function called `linearSearch`

that accepts a value that is an integer or string and an array as parameters. The function will search every element in the array for the value and return the position of the value in the array if it is found. If the value is not in the array, it will return `-1`

.

### Pseudocode for Linear Search

Set found to false Set position to −1 Set index to 0 while found is false and index < number of elements if list[index] is equal to search value Set found to true Set position to index else Add 1 to index return position

### Step-by-Step Explanation of Linear Search

Imagine our input to the linear search is `[1,9,13,16,3,4,0,12]`

. If the value we’re searching for is `16`

, the above logic would return `3`

. And, if we search for `11`

, the above logic will return `-1`

. Let’s break it down.

We initialise the algorithm by setting `found`

to `false`

, `position`

to `-1`

, and `index`

to `0`

. Then we iterate:

Step | `index` |
`list[index]` |
`position` |
`found` |
---|---|---|---|---|

1 | `0` |
`1` |
`-1` |
`false` |

2 | `1` |
`9` |
`-1` |
`false` |

3 | `2` |
`13` |
`-1` |
`false` |

4 | `3` |
`16` |
`3` |
`true` |

If we follow the above logic for an element that is not present in the array, you’ll see the code returning -1, since `found = false`

, and `position = -1`

till the end.

### Javascript Implementation of Linear Search

Here is a JavaScript implementation of the linear search algorithm:

function linearSearch(value, list) { let found = false; let position = -1; let index = 0; while(!found && index < list.length) { if(list[index] == value) { found = true; position = index; } else { index += 1; } } return position; }

### Properties of Linear Search

It is important to note that the linear search algorithm does not need to use a sorted list. Also, the algorithm can be customised for use in different scenarios like searching for an array of objects by key. If you have an array of customer data that includes keys for the first and last name, you could test if the array has a customer with a specified first name. In that case, instead of checking if `list[index]`

is equal to our search value, you would check for `list[index].first`

.

### Time Complexity of Linear Search

The best-case time complexity is achieved if the element searched is the first element in the list. Now, the search would complete with a single comparison. Hence, the best-case time complexity would be **O(1)**.

The worst-case time complexity occurs if the element searched is the last element or is not present in the list. In this case, the search has to compare all elements in the array. We say that the input data has length **n**, which means the overall time complexity is **O(n)** due to the n comparisons made.

In the example above, I used the `linearSearch`

function on an array with eight elements. In the worst case, when the search value is not in the list or is at the end of the list, the function would have to make eight comparisons. Because our array is so small, there is no need to optimise using a different algorithm. However, beyond a certain point, it is no longer efficient to use a linear search algorithm, and that’s when using a binary search algorithm would be better.

The average time complexity of linear search is also **O(n)**.

### Space Complexity of Linear Search

The overall space complexity of this algorithm is equivalent to the size of the array. Hence, **O(n)**. You don’t need to reserve any additional space for completing this algorithm.

## Binary Search

Imagine you are playing a number guessing game. You are asked to guess a number between 1 and 100. If your number is too high or too low, you will get a hint.

What would your strategy be? Would you choose numbers randomly? Would you start with 1, then 2, and so on until you guessed correctly? Even if you had unlimited guesses, you want to make the correct guess in as few tries as possible. Therefore, you might start by guessing 50. If the number is higher, you could guess 75. If it is lower, then that means the number is between 50 and 75, and you would choose a number that’s in the middle. You would go on like this until you arrived at the correct number. This is similar to how binary search works.

There are two ways of implementing binary search:

- iterative method
- recursive method

### Pseudocode for Iterative Binary Search

Here’s some pseudocode that expresses the binary search using the iterative method:

do until the low and high pointers have not met or crossed mid = (low + high)/2 if (x == arr[mid]) return mid else if (x > arr[mid]) low = mid + 1 else high = mid - 1

### Pseudocode for Recursive Binary Search

Here is the pseudocode for implementing the binary search using the recursive method.

binarySearch(arr, x, low, high) if low > high return False else mid = (low + high) / 2 if x == arr[mid] return mid else if x > arr[mid] return binarySearch(arr, x, mid + 1, high) else return binarySearch(arr, x, low, mid - 1)

Regardless of the technique used, the binary search algorithm always uses the divide and conquer approach.

### Step-by-Step Explanation

Let’s consider an array `[1,9,13,16,3,5,0,12]`

where the `searchValue`

is `13`

.

We start with a sorted array as required to perform a binary search. Note that sorting the array is expensive, but once it’s done, the array can be efficiently searched many times.

Now, the high and low pointers will be set to the first and last elements respectively. The mid pointer is set to the index given by `(low - high) / 2`

.

Since `searchValue > mid`

, we need to search the right side of the array. So we set the `low`

pointer to be just after `mid`

, and `mid`

is reset to be between the `low`

and `high`

pointers.

Again, the target value is towards the right of the array. Once again, we adjust the low and high pointers. Now the low and mid pointers are the same.

Now, the `searchValue`

is found at `mid`

, which means we have reached the end of our search!

Step | `low` |
`mid` |
`high` |
`list[mid]` |
---|---|---|---|---|

1 | `0` |
`3` |
`7` |
`5` |

2 | `4` |
`5` |
`7` |
`9` |

3 | `6` |
`6` |
`7` |
`13` |

### Javascript Implementation of Binary Search

Now let’s code the binary search algorithm in JavaScript!

We’ll create a function, `binarySearch`

, that accepts a value and an array as parameters. It will return the index where the value occurs in the list if found. If the value is not found, it returns -1. This is our implementation written in JavaScript:

//note that list must be sorted for this function to work function binarySearch(value, list) { let low = 0; //left endpoint let high = list.length - 1; //right endpoint let position = -1; let found = false; let mid; while (found === false && low <= high) { mid = Math.floor((low + high)/2); if (list[mid] == value) { found = true; position = mid; } else if (list[mid] > value) { //if in lower half high = mid - 1; } else { //in in upper half low = mid + 1; } } return position; }

### Time Complexity

One of the main reasons why we use binary search for finding elements in an array would be its time complexity. In a best-case scenario, the time complexity for Binary Search is **O(1)**. This happens when the element in the middle of the array matches the search element.

At worst, the time complexity for searching an element using binary search is **O(log n)**—much less than **O(n)** for large values of n. To get an idea of how much slower growing **log(n)** is than **n**, here is a table of typical values of **log(n)**.

n | log(n) |

1 | 1 |

8 | 3 |

1024 | 10 |

1,000,000 | 19.9 |

1,000,000,000,000,000,000 | 59.8 |

So, as you can see, the bigger n gets, the more the improvement of a binary search over a linear search.

The average** **case time complexity is also **O(log n)**, for searching an item using binary search.

### Space Complexity

The space complexity for implementing the binary search is again **O(n)**.

### Properties of Binary Search

Unlike linear search, binary search uses a sorted list. That lets us use a “divide and conquer” algorithm to solve the problem.

## Conclusion

In this tutorial, we saw how to implement a linear search and a binary search algorithm. The linear search algorithm is simpler and doesn’t require a sorted array. However, it is inefficient to use with larger arrays. In the worst case, the algorithm would have to search all elements making n comparisons (where n is the number of elements).

The binary search algorithm, on the other hand, requires you to sort the array first and is more complicated to implement. However, it is more efficient even when considering the cost of sorting. For example, an array with 10 elements would make at most 4 comparisons for a binary search vs. 10 for a linear search—not such a big improvement. However, for an array with 1,000,000 elements, the worst case in binary search is only 20 comparisons. That’s a huge improvement over linear search!

Knowing how to use binary search isn’t just something to practice for an interview question. It’s a practical skill that can make your code work much more efficiently.

*This post has been updated with contributions from Divya Dev. Divya is a front-end developer more than half a decade of experience. She is a grad and gold medalist from Anna University.*