Applying binary search in JavaScript
Starting from linear search
One of the first things you learn when you start programming (at least in JS) is the famous “for-loop” — a kind of linear search — with which you can traverse a set of values to find a particular one or test for a subset that meets specific criteria. For the most part, that works quite well, like when you are developing low-traffic apps or working with small datasets. But as complexity and performance requirements increase, you will need to reach for a different algorithm like binary search. Before doing that, though, let’s first take a quick look at a typical “for-loop” below. If you are in a hurry to get into binary search, scroll to the last section, which includes a simple JS binary search.
const arr = [2,4,3,5,7,6,8,5,10]let target = 8for(let i = 0; i < arr.length; i++){// do something with arr[i] to find value 8 in the array}
In the example above, we are iterating over every element in the dataset in sequence and checking whether we can find the target value. The value we are looking for can be anywhere inside the array. In this example, we found the number after seven iterative checks since the target is at the 7th index in the array. Of course, had the target (the number 8), been located at the start of the array, we could say that the foor-loop search would have run relatively fast as it would find the target only after one or few iterations.
We can actually depict this mathematically using the big-theta notation. Had the number 8 been positioned at the first index of our array, we would say that our for-loop’s runtime would be Θ(1). However, as you can see, it’s instead located at the end of the array. Therefore, it’s safe to say that the maximum time it takes the for-loop to run depends on the length of the array or in mathematical terms; Θ(n). Both Θ(1) and Θ(n) represent the minimum and maximum runtime that our for-loop can operate in. As you can already tell, theta-notation doesn’t help us accurately benchmark our for-loop against other algorithms as it could massively vary within those bounds. It’s important to note, however, that the upper bound Θ(n) can more dramatically affect the performance of our loop if it gets significantly large. Just think that according to ECMAScript — the specification behind JavaScript — an array can have a length of up to 4.29 billion elements! (Look at ECMA section 6.1.7 in the Object Type section — yes arrays are objects in JS but more on that another time).
While theta has provided some insight into the runtime performance of our for-loop, to correctly judge the complexity of an algorithm’s runtime while also considering the best and worst-case scenarios of the Θ boundaries, we need to use a different notation. Enter big-O notation. With big-O, our for-loop’s runtime is instead O(n). This notation now clearly depicts that the linear search algorithm’s performance is particularly susceptible to increases in the total number of elements in the dataset. Now keep this in mind as we look at how binary search’s runtime differs.
Binary Search explained
Unlike linear search where we checked every number in the array, binary search minimises the number of elements we have to iterate over by continually halving the dataset and only looking for the target in either of the two halves. To achieve this, binary search comes with a necessary prerequisite. The dataset must be first sorted in ascending or descending order before searching. In practice, that means that if we are trying to find the number 8 in an array, we can test one number from the dataset and ask whether that number is less than or greater than 8. Since we sorted the numbers in the array, we can assess whether the number we are looking for comes before or after the number we have just checked.
For example, if we just checked a location in the array and we found the number 5, we could safely ignore all numbers before it since we discern we won’t find 8 in that range. Thus we won’t have to spend time searching through all those numbers like we did with linear search at the beginning. Also, since our search is binary in nature (i.e., made of two parts), we must check the mid-location of the array so that we can split the dataset into two halves and decide which one to search into next. Then we can again test the mid-location of that specific half until we find the target or run out of halves. Let’s visualise these steps with pseudocode:
// STEP 1
first sort the array and establish a given target to search for// STEP 2
define the current search area and its midpoint// STEP 3
repeat the following until we either find 8 or run out of search area: a. check if the value in this point equals the target b. if it does, great we found it!
c1. if the midpoint is greater than the target, halve the search area by searching to the left of the midpoint c2. if the midpoint is lower than the target, halve the search area by searching to the right of the midpoint
Now let’s start writing our JS code for each step.
Simple Binary Search in JavaScript
Step 1: Sort the array and establish a given target to search for
Keep in mind that for Binary Search to work, we must first sort our array of numbers so that we can assess whether the target we are looking for is lower or higher than than the number we last checked. Doing so will help us decide which of the two halves of our search area to look into next — we will implement this in step 3. It’s also vital to remember sorting when we consider the Binary Search’s runtime. No matter how well BS works in isolation, you must also account for the additional runtime of sorting the data first. More on this later, for now, we will use JavaScript’s built-in, array.sort method to prepare our data for BS:
const arr = [12,5,7,3...];const sortedArray = arr.sort()
// [1,3,5,5,7,8,11,12,14,14,15,16,16,17,17,17,17,18,19,19,19];let target = 18;
Step 2: Define the current search area
As you can tell from the pseudocode, we now need to define some variables to track how much of the data we have searched. Now we could use a variable to store how many numbers are left to go through just like we did with linear search (i.e., when we defined that we should iterate until i < arr.length).
But remember, the whole point of binary search is to avoid looking into every location of the dataset. BS must repeatedly halve the area of our search until we succeed or run out of space to search. So instead of tracking how many numbers we have iterated over, we will only keep track of the start and end-points of every halve we search into at any given point and ignore what lies outside it. Since at first, we begin with the whole array before splitting it, the end-point of our search will be of value 20 ( the last index in our array), and the start-point will be 0 (the first index in our array). Also, since we must only check the mid-point, we need to track this as well. So let’s update our pseudocode like so:
const sortedArray = [1,3,5,5,7,8,11,12,14,14,15,16,16,17,17,17,17,18,19,19,19];let target = 18;// start index of the array we are searching in
let start = 0;// end index of the array we are searching in
let end = arr.length - 1;// midpoint to check for the target
let middle = Math.floor(start + end / 2);
Now, let’s work on the halving logic.
Step 3: Repeat the “checking-halving” logic until we either succeed or run out of search area
const sortedArray = [1,3,5,5,7,8,11,12,14,14,15,16,16,17,17,17,17,18,19,19,19];let target = 18;let start = 0;
let end = arr.length - 1;
let middle = Math.floor(start + end / 2);// a. check if the value in this point equals the targetif(arr[middle] === target){
// b. if it does, great we found it!
return true;
}
// c1. if the midpoint is greater than the target, halve the search area by searching to the left of the midpointelse if(arr[middle] > target){
end = middle - 1
}// c2. if the midpoint is lower than the target, halve the search area by searching to the right of the midpointelse if(arr[middle] < target) {
start = middle + 1;
}
We need to repeat these steps with a while loop until we either find the target or run out of area to search in. We will know that we run out of search area when the start boundary becomes less than or equaly to the end boundary of the search area (i.e. every half we search into), leaving no more values to search for in between them. See below for the full solution with added logging to track what’s happening at every iteration.
Solution
The binary Search runtime
Analysis coming soon
