Binary Search JavaScript: A Guide

How to Code a Binary Search in JavaScript

Searching algorithms makes life so much easier as a programmer. Doing so makes it easy to find a particular item inside a data set of tens, hundreds, or thousands of items.

One of the most popular forms of searches is the binary search. This search quickly finds an item in an array. Every time the search looks through an item, it reduces the number of items that are left to be searched by half.

In this guide, we’re going to talk about what binary searches are and how they work. We’ll then go on to implement a binary search using two different approaches: iterative and recursive.

Let’s build a binary search algorithm in JavaScript!

What is a Binary Search?

A binary search is a computer science algorithm that searches for an item in a sorted array.

It starts in the middle of an array and checks whether the middle item is less than, equal to, or greater than the number for which you are searching.

If the number is smaller, the algorithm knows to keep searching in the left half of the array, where the smaller numbers are; if the number is larger, the algorithm will focus on the right half of the array. Binary searches only work on sorted lists.

Binary searches are more efficient than linear searches. This is because every time a search is made the number of items left to search in the list is reduced by half.

How to Use a Binary Search

A binary search is easy to understand once you get the hang of it.

Before we implement a binary search algorithm, let’s walk through one step-by-step. We’re going to find the number “9” in a list. Let’s start with a sorted list:

First, we need to find the middle number and assign it to a variable. This is found by calculating the sum of the first and last numbers and dividing it by two. We’ll call this variable “middle”:

8 is our middle number. Then, we can compare the middle number to the one for which we are searching. If the middle number is equal to the one we are searching for, our search can stop.

In this example, 8 is not equal to 9. Our search continues.

Next, we need to compare whether the middle number is greater than 9. It is not.

This tells us that the number for which we are searching must be after the middle number. 9 is greater than 8 in a sorted list. We are going to set our starting number to be equal to the middle number. This is because we know that the number for which we are searching does not come before the middle number.

If the number for which we are searching is smaller, we would set the end number to be equal to the middle number. Because the number is smaller than the middle number, we could focus our search on the lower half of the list.

The binary search repeats again on the top half of the list because 9 is greater than 8:

We find the middle number again. This is 9. We can compare 9 to the number for which we are searching. 9 is equal to the number for which we are searching.

This means our search can stop. We’ve successfully found the number 9 in our list!

How to Implement a Binary Search in JavaScript

Binary searches can be implemented using an iterative or recursive approach.

Iterative Binary Search

An iterative binary search uses a while loop to find an item in a list. This loop will execute until the item is found in the list, or until the list has been searched.

Let’s start by writing a function that performs our binary search:

function binarySearch(array, numberToFind) {
	let start = 0;
	let end = array.length - 1;

	while (start <= end) {
		let middle = Math.floor((start + end) / 2);

		if (array[middle] === numberToFind) {
			return middle;
		} else if (array[middle] < numberToFind) {
			start = middle + 1;
		} else {
			end = middle - 1;
		}
	}

	return -1;
}

We start by defining two variables: start and end. These keep track of the highest and lowest values our search is working with. We use a while loop that runs until the start number is greater than the end number. This loop calculates the middle number between start and end in the list.

If the number for which we are searching is equal to the middle number, the middle number is returned to our main program. If the number is smaller, the start value is set to be equal to the middle number plus one. These comparisons are performed using an if statement.

"Career Karma entered my life when I needed it most and quickly helped me match with a bootcamp. Two months after graduating, I found my dream job that aligned with my values and goals in life!"

Venus, Software Engineer at Rockbot

Find Your Bootcamp Match

Otherwise, the end number is set to be equal to the middle number minus one. If our number is not found after the while loop has run, -1 is returned. We call this a base condition. In our main program, we’ll check if the number returned is equal to -1. If it is, it means our number could not be found.

Our function does not work just yet. We need to write a main program that calls it:

let numbers = [2, 6, 8, 9, 10];
let toFind = 9;
let findNumber = binarySearch(numbers, toFind);

if (findNumber !== -1) {
	console.log(`${toFind} has been found at position ${findNumber}.`);
} else {
	console.log(`${toFind} has not been found.`);
}

We’ve defined a list of numbers through which to search and the number that we want to find in our list. Next, we have called the binarySearch function. This will perform our search. The search will return either -1 or the position of the item for which we are searching.

-1 denotes that an item could not be found. If an item is not found, the contents of our else statement are executed. Otherwise, the contents of the if statement are run.

Let’s run our code:

9 has been found at position 3.

This tells us that our search has been successful!

Recursive Binary Search

A recursive binary search is considered more elegant than an iterative one. This is because binary searches perform the same operation over and over again on a list. This behavior can be implemented using a recursion algorithm.

Open up a new JavaScript file and paste in this code:

function binarySearch(array, numberToFind, start, end) {
	if (start => end) {
		return -1;
	}

	let middle = Math.floor((start + end) / 2);

	if (array[middle] === numberToFind) {
		return middle;
	} else if (array[middle] < numberToFind) {
		return binarySearch(array, numberToFind, middle + 1, end);
	} else {
		return binarySearch(array, numberToFind, start, middle - 1);
	}
}

This code makes the same comparisons as our first search. It checks whether the middle number is equal to, greater than, or less than the number for which we are searching.

At the start of our function, we have used an if statement to check if the start number is greater than the end number. If it is, this means our item could not be found in the list we have specified. We return -1 to the main program if this is the case.

If the number we’re looking for is the same as the middle number, the middle number is returned to the main program. If the number we’re looking for is greater or less than the middle number, our binarySearch function is run again. This continues until our item is found.

To run this function, we’re going to need to make a change to our main program:

let numbers = [2, 6, 8, 9, 10];
let toFind = 9;
let findNumber = binarySearch(numbers, toFind, 0, numbers.length - 1);
… 

We need to pass in two additional parameters: the values of “start” and “end”. The value of “start” is equal to 0. The value of “end” is equal to the length of the list minus one.

Let’s run our code and see what happens:

9 has been found at position 3.

Our binary search was successful! It uses the same underlying algorithm as the iterative approach. The difference is that the binary search is performed by using a function which calls itself until the item is found or until the list is fully searched, whichever comes first.

Conclusion

Binary searches make it easy to find an item in a list. Every time a search is executed, the number of items left to search in a list is reduced by half. This makes a binary search more efficient than a linear search.

Now you’re ready to implement a binary search in JavaScript like an expert!