# 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.

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

**. Check out my guide to Linear Search implementations in JavaScript for a quick refresher:**

*Binary Search*# 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

**and their implementations use common patterns that will constantly pop up in the code you read and write as a software developer.**

*Linear Search Algorithms*## How it works:

- A BSA will only work when its run against a
list.*sorted* - It also needs a target element to look for (ex. 5).
- It then has to find (and track) the start, middle and end of the list.
- It will check if the middle number equals the target number.
- If the middle equals the target number it will exit the algorithm.
- 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
half of the list.*second* - 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
half of the list.*first* - 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 3Is 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

**or a**

*half-interval search***. As a result, this algorithm has a slightly better time-complexity than the linear search algorithm. The**

*binary-chop***runs in logarithmic time with a worst case performance of**

*BSA***O(log2 n)**.

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

**A helpful animation by ****Y. Daniel Liang** — http://www.cs.armstrong.edu/liang/animation/web/BinarySearch.html

**Straight forward explanation with images** — https://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// update the midIndex after the iterators have changed

while (leftIndex <= rightIndex) {

midIndex = Math.floor((leftIndex + rightIndex) / 2);// If the element at the midIndex equals target return 1// If target < than mid element reduce the right index by 1

if (sortedArr[midIndex] === target) {

return 1;

// If target > than mid element increase the left index by 1

} else if (target < sortedArr[midIndex]) {

rightIndex = midIndex - 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// Find the mid index of the array

const recursiveSearch = (left, right, arr, tar) => {

// If the left is less than the right continue the loop

let mid = Math.floor((left + right) / 2);

// If we find the target return 1, base case

if (left <= right) {

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: