The Startup
Published in

The Startup

Binary Search Algorithm 101

Let’s find things… fast-ish. This is a thorough look at Binary Search Algorithm implementations in JavaScript (Iterative and Recursive). Enjoy.

Photo by Jon Tyson on Unsplash

Building a search function is something that every developer has to do. In fact, basic Linear Search functions are usually some of the first patterns that developers learn to write. If you are unfamiliar with this concept I suggest you get up to speed with the basics of Linear Search Algorithms before you dig into Binary Search. Check out my guide to Linear Search implementations in JavaScript for a quick refresher:

The Concept

Ok, so what is a Binary Search Algorithm (BSA)?

This algorithm allows you to find out if a certain element exists within a larger list. It will help you answer a question like this: Does the number 5 exist in a list of 10, 000 random numbers (that have been sorted)?

Why should you care?

Simply put, BSA’s are (usually) faster than Linear Search Algorithms and their implementations use common patterns that will constantly pop up in the code you read and write as a software developer.

How it works:

  1. A BSA will only work when its run against a sorted list.
  2. It also needs a target element to look for (ex. 5).
  3. It then has to find (and track) the start, middle and end of the list.
  4. It will check if the middle number equals the target number.
  5. If the middle equals the target number it will exit the algorithm.
  6. Else if the middle is less than the target number it will shrink the search area and ONLY look for the target number in the second half of the list.
  7. Else if the middle is greater than the target number it will shrink the search area and ONLY look for the target number in the first half of the list.
  8. The BSA will repeat this process until the middle number is equal to the target number OR the array is empty.

Here is a step-by-step example of a BSA using an array:

// sorted array
let array = [1,2,3,4,5];
// number to find
let target = 5;
starting element at index 0 is number 1
ending element at index 4 is number 5
middle element at index 2 is number 3
Is the middle element (3) === to the target (5)?
No.
Is the target greater or less than the middle number?
The target (5) is greater than the middle (3).
So we know to only look on the right side of the array.
--> [4, 5]
Is the middle element (4) === to the target (5)?
No.
Is the target greater or less than the middle number?
The target (5) is greater than the middle (4).
So we know to only look on the right side of the array.
--> [5]
Is the middle element (5) === to the target (5)?
Yes.
This array contains the target element!

So to summarize what is going on in the walkthrough above, the BSA is basically breaking down the search area by half, after each iteration. This is why it’s sometimes referred to as a half-interval search or a binary-chop. As a result, this algorithm has a slightly better time-complexity than the linear search algorithm. The BSA runs in logarithmic time with a worst case performance of O(log2 n).

An Introduction to the Time Complexity of Algorithms (Aditya Dehal @ freeCodeCamp)

If you are still a bit confused here are some resources to help you visualize the process:

A helpful animation by Y. Daniel Lianghttp://www.cs.armstrong.edu/liang/animation/web/BinarySearch.html

Straight forward explanation with imageshttps://www.w3resource.com/python-exercises/data-structures-and-algorithms/python-search-and-sorting-exercise-1.php

Implementation

Ok, let’s get into the fun stuff and actually code this in JavaScript.

Iterative Function

The first (most common) approach to the BSA is an iterative implementation. Refer to the step-by-step example above if you get lost in the code. If the target is found in the array the function returns 1, if not it returns -1.

const binarySearch = (sortedArr, target) => {

// Create iterators for left, right and mid indexes
let leftIndex = 0;
let midIndex = 0;
let rightIndex = sortedArr.length - 1;
// While the left iterator is less than or equal to the right
// iterator continue the loop
while (leftIndex <= rightIndex) {

// update the midIndex after the iterators have changed
midIndex = Math.floor((leftIndex + rightIndex) / 2);
// If the element at the midIndex equals target return 1
if (sortedArr[midIndex] === target) {
return 1;

// If target < than mid element reduce the right index by 1
} else if (target < sortedArr[midIndex]) {
rightIndex = midIndex - 1;

// If target > than mid element increase the left index by 1
} else {
leftIndex = midIndex + 1;
}
} // If target never equals midIndex return -1
return -1;
};

This implementation is highly dependent on the current status of the iterators after each loop. If you are having issues understanding the code I suggest using console.log() with the iterators to track how and when they change.

Recursive Function

This is a fun implementation that uses recursion to execute the BSA. We use 2 functions to achieve the same result. Keep in mind that you can implement these functions in many ways.

const binarySearch = (sortedArr, target) => {  // Create the left and right indexes
let leftIndex = 0;
let rightIndex = sortedArr.length - 1;
// Declare the recursive function
const recursiveSearch = (left, right, arr, tar) => {

// Find the mid index of the array
let mid = Math.floor((left + right) / 2);

// If the left is less than the right continue the loop
if (left <= right) {

// If we find the target return 1, base case
if (arr[mid] === tar) {
return 1;
// If target is greater or less than target call the function
// again with an updated iterator (mid + 1) or (mid - 1)
} else if (tar > arr[mid]) {
return recursiveSearch(mid + 1, right, arr, tar);
} else {
return recursiveSearch(left, mid - 1, arr, tar);
}
};
// If tar not found return -1
return -1;
};
// Call the recursive function we declared above
recursiveSearch(leftIndex, rightIndex, sortedArr, target);
};

Bam! We did it, that is the recursive implementation of the BSA in JavaScript. If you are still struggling with the recursive part of the function check out this awesome article that breaks down recursion:

Conclusion

Thanks for reading! If you want a slightly more detailed look at the code above check out my Github Repo and play around with the functions:

https://github.com/twjsanderson/binarySearchAlgo

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store