# The Binary Search Algorithm in JavaScript

In this post, I'll compare linear search and binary search algorithms. You'll see pseudocode for each algorithm, along with examples and a step-by-step guide to implementing each.

## 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. For example, calling `linearSearch(1, [3, 4, 2, 1, 5])`

would return 3, and calling `linearSearch(0, [3, 4, 2, 1, 5])`

would return -1.

Here's some pseudocode for our function:

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

### 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; }

It is important to note that the linear search algorithm does not need to use a sorted list. Also, the algorithm can be customized 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`

.

In the example above, I used the `linearSearch`

function on an array with five 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 five comparisons. Because our array is so small, there is no need to optimize by using a different algorithm. However, beyond a certain point, it is no longer efficient to use a linear search algorithm, and that is when using a binary search algorithm would be better.

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

Unlike linear search, binary search uses a sorted list. To search for a value, you first compare the value to the middle element of the list. If they are equal, the search value has been found. If the search value is greater than the middle element, you search the top half of the data. You then compare the middle element of this section to the search value. Alternatively, if the item is less than the middle element, you search the bottom half of the list and compare its middle value. The list is repeatedly divided in half until the element is found or there are no more items to search.

To search for 9 in the list:

1 2 3 4 5 6 7 8 9 10

We first find the middle element. This is the element at position `Math.floor((first + last)/2)`

, where `first`

is the first index, and `last`

is the last index. We choose to round down so that if the result is a fraction, it becomes a whole number. The middle element in this list is 5. Our search value 9 is greater than 5, so we search the list:

6 7 8 9 10

The middle element of this portion is 8. Nine is greater than 8, so we search the list:

9 10

The middle element is 9, so we can stop our search here.

Here's some pseudocode that expresses the above algorithm for binary search:

Set first to 0 Set last to the last index in the list Set found to false Set position to −1 while found is false and first is less than or equal to last Set middle to the index halfway between first and last if list[middle] equals the desired value Set found to true Set position to middle else if list[middle] is greater than the desired value Set last to middle − 1 else Set first to middle + 1 return position

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

function binarySearch(value, list) { let first = 0; //left endpoint let last = list.length - 1; //right endpoint let position = -1; let found = false; let middle; while (found === false && first <= last) { middle = Math.floor((first + last)/2); if (list[middle] == value) { found = true; position = middle; } else if (list[middle] > value) { //if in lower half last = middle - 1; } else { //in in upper half first = middle + 1; } } return position; }

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

Envato Tuts+ tutorials are translated into other languages by our community members—you can be involved too!

Translate this post