Binary search in JavaScript. Practical example

What is binary search?

When you need to search in an array, the simplest way would be to use indexOf () or perhaps a for () loop. Any of these methods will begin to iterate over the array from the beginning and go through each element of the array until the desired value is found.

Now compare this to binary search .

Binary search allows you to search in a sorted array by repeatedly splitting the array in half.

A binary search is performed by checking whether the search value is greater than , less than, or equal to the average value in our array:

• If it is smaller, we can remove the right half of the array.
• If it is larger, we can remove the left half of the array.
• If it is equal, we return the value

But the bottom line is that the array must be sorted, i.e. the values ​​must be in the correct order for the binary search to work correctly.

When working with large amounts of data, it is much more efficient to use binary search, since at each iteration half of the unnecessary array values ​​are deleted, and not just one inappropriate value.

Project

I recently posted an article on how I wrote an interactive 30-day bitcoin price chart from the React API .

One of the most important aspects of a chart is a tooltip that displays relevant data when you hover over the chart. When you move the mouse on the tooltip, data from the nearest point in the chart is updated. Example:



How does it work?

We have an array of all coordinates and their corresponding data. The coordinates are inside the object, and each object has an svgX key. It looks something like this:

svgData = [
  {svgX: 1367.844, data...},
  {svgX: 1684.478, data...},
  {svgX: 1168.474, data...},
  {svgX: 1344.854, data...},
  // etc.
]

Initially, I used a simple for loop to compare the current X coordinate of the mouse cursor with all svgX values ​​in my data array.

Cycle

This is what the for loop code looks like. We iterate over all svgX values, and an object with a value closer to the X coordinate of the mouse cursor is the object whose data we want to show.

const {svgWidth} = this.props;
let closestPoint = {};
 for(let i = 0, c = svgWidth; i < svgData.length; i++){
   if ( Math.abs(svgData[i].svgX — this.state.hoverLoc) <= c ){
     c = Math.abs(svgData[i].svgX — this.state.hoverLoc);
     closestPoint = svgData[i];
   }
 }

First we get the width of our svg element and create an empty object to store our nearest point.

const {svgWidth} = this.props;
let closestPoint = {};

Then we iterate over the data array. Each svgX value of an object in our array is compared with the X coordinate of the mouse cursor. If the current iteration of the loop has a value closer to the cursor than any other iteration, then this point is set as our closest point.

With a small amount of data, this method is relatively fast. However, if we have a large amount of data, this option will no longer be as effective.

Binary search

The following is an example binary search code for finding the closest value:

const binarySearch = (data, target, start, end) => {
  if(end < 1) return data[0];
  const middle = Math.floor((start + (end - start)/2);
  if (target == data[middle].svgX) return data[middle];
  if (end — 1 === start) return Math.abs(data[start].svgX — target) > Math.abs(data[end].svgX — target) ? data[end] : data[start]; 
  if (target > data[middle].svgX) return binarySearch(data,target,middle,end);
  if (target < data[middle].svgX) return binarySearch(data,target,start,middle);
}
let closestPoint = binarySearch(data,target, 0, data.length-1)

We need five main components for our binary search:

1. data - data. An array of objects.
2. target is the target. The location of the mouse cursor (x coordinate).
3. start is the beginning. The starting position in the array for the current iteration of the binary search.
4. end - the end. The end position in the array for the current iteration of the binary search.
5. middle is the middle. The middle of the array for the current iteration of the binary search.

I know this is a bit confusing, so let's look at an example that simplifies the code above. In this example, our target value is 3.7. We will search in an array of five increasing numbers from 1 to 5.

As can be seen from the above code in line 10, when starting a binary search, we pass the entire data array, mouse object, start position 0 and end position equal to the full size of the array :

When we have our data, we will find the middle of the array by dividing by two, the sum from the starting and ending positions. In order not to get a fraction, the resulting number is rounded down:

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

Thus, mid 0 + (4-0) / 2 rounded down = 2:

We remember that for this example, our target value is 3.7. After we find the middle position, we check if it is equal to our target value. If so, we return the object, and you're done!

if (target == data[middle].svgX) return data[middle];

Unfortunately, the average value of the array = 3. And our goal is 3.7.

Next, we will check whether our final position - 1, coincides with our initial position:

if (end — 1 === start) {
  return Math.abs(data[start].svgX — target) > Math.abs(data[end].svgX — target) ? data[end] : data[start];
}

This condition will work when our array is reduced to two final values, and our goal is between them. In this case, we return the near value.

At the current iteration, the condition will return false.

Next, we check whether our target value is larger than the average:

if (target > data[middle].svgX) return binarySearch(data,target,middle,end);

This is our case! The target value of 3.7 is greater than the average of 3. We can get rid of the first two values ​​in our array:


Using recursion, we return a new call to the binarySearch () function. We pass our array to the function, the target value is 3.7 , the average value as the initial position and the final value as the final position.

Our new binarySearch () call will search from position 2 to data.length-1:


The function finds a new middle position data [3]:

Since our target value of 3.7 is less than the average value of 4, we discard the right side of the array and return a new call to binarySearch (). This time our initial position remains data [2], and the final position changes to the average data [3].

We have reached the moment when our condition is fulfilled:

if (end — 1 === start) {
  return Math.abs(data[start].svgX — target) > Math.abs(data[end].svgX — target) ? data[end] : data[start];
}

Since our final value minus one equals our initial value, we know that the target value is somewhere in between. We must return an array element whose value is closer to the value of 3.7 . Since 4 (the final value) is closer, we respectively return the corresponding element: data [3].

Speed ​​test

If the amount of data is small, recursion may be slower than the for loop. When testing on jsperf with 10 elements, the recursive function is on average 3% slower than the for loop. However, with 10,000 elements, the for loop is 72% slower than the recursive function. This means that recursion is almost twice as fast as the for loop, and that is a huge time saver!

I hope you now understand the basics of binary search in JavaScript!