Binary search in javascript. Practical example

What is binary search?

When you need to perform a search in an array, the easiest way is to use indexOf () or possibly a for () loop. Any of these methods will begin to iterate through 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 a sorted array by splitting an array in half.

A binary search is performed by checking whether the value we are looking for 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 delete 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, that is, 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 values ​​of the array are deleted, and not just one inappropriate value.

Project

I recently published an article about how I wrote an interactive 30-day bitcoin price chart with an API on React .

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



How it works?

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 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 the svgX values ​​in my dataset.

Cycle

This is what the for loop code looks like. We iterate over all svgX values, and an object with a value that is 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 hold our nearest point.

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

Then we iterate over the data array. Each svgX object value in our array is compared with the X coordinate of the mouse cursor. If the current loop iteration matters closer to the cursor than any other iteration, then this point is set as our nearest 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

Below is an example of a binary search code to find the nearest 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 basic components for our binary search:

1. data - data. Array of objects.
2. target is the target. The location of the mouse cursor (x coordinate).
3. start - the beginning. The starting position in the array for the current iteration of the binary search.
4. End is the end. The final position in the array for the current iteration of the binary search.
5. middle - 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 will be 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 launching a binary search, we transfer the entire data array, the mouse object, the starting position 0 and the end position equal to the full size of the array:

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

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

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

We remember that for this example, our target value is 3.7. After we have found 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 check whether our final position is 1, 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.

On the current iteration, the condition returns false.

Next, we check whether our target value is greater than 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 binary call to the binarySearch () function. We pass our array to the function, the target value is 3.7 , the average value as the starting position and the final value as the ending position.

Our binary binary search () will search from position 2 to data.length-1:


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

Since our target value of 3.7 is less than the average of 4 , we discard the right side of the array and return a new call to the binarySearch () function. This time, our starting position remains data [2], and the ending 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 between them. We must return an array element whose value is closer to the value of 3.7 . Since 4 (the final value) is closer, then accordingly we return the corresponding element: data [3].

Speed ​​test

If the amount of data is small, the 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 an element count of 10,000, the for loop is 72% slower than the recursive function. This means that recursion is almost twice as fast as the for loop, and this is a huge time saver!

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