Data Structures and Algorithms 102: Javascript Binary Search Algorithm
Tags: datastructures, algorithms, beginners, tutorial
Published: 2022-07-01 00:36:04

## Introduction

In my previous article [Data Structures and Algorithms 101](https://dev.to/nemwelo/data-structure-and-algorithm-4gid) you can read an introduction to what is data structures and algorithms.

In this article I will deep dive into Binary search algorithm. Searching algorithms falls into either sequential or interval search.Linear and binary searches are the commonly two simple as well as easy to implement algorithms. 

Binary search is faster than linear search(where search is done in a sequence on every element). Here, am going to walk you through binary search algorithm and:
- define what is a binary search
- how to implement it  
- where it can be used

### What is binary search algorithm?

Binary search algorithm is a divide-and-conquer algorithm that divides elements in a sorted array roughly into half every time it checks for the target element we are searching.Simply put,we divide the problem into simpler problems until it becomes simple enough to solve them directly.

### How do we implement a binary search?

You can implement most of the algorithms in two ways:
 - Iteratively or 
 - Recursively

__Iterative version__ of the algorithm involves a loop which repeats some steps until the stopping condition is met whereas __recursive version__ uses a function that calls itself. I will be covering iterative version in this article.

We begin by implementing a function in JavaScript that search element value and returns its index:
```js
       const binarySearch = (elements, value) => {
       // Add other code

          }
```

Assuming we have a sorted array,set the lower(__startIndex__) and upper(__endIndex__) boundaries at the appropriate ends of the sequence:

```js 
 const arr =  [0,5,12,23,34,35,46,47,58];
 const binarySearch = (elements,value) => {    
       let startIndex = 0;
       let endIndex = arr.length - 1;
        
         }   
```

Now we will identity the middle element to see if it has the value we want to search.We calculate this middle value (__middleIndex__) by taking the average of both boundaries:
    

```js
   let middleIndex = Math.floor((startIndex + endIndex) / 2 );
```

Here, you notice I have used the __Math.floor()__ function to help handle an __odd__ and __even__ number of element in the bounded range by flooring the result.

Now,we compare that middle element with the value we are looking for as a key:

> 
 - __When the key is less than the middle element,we search in the left half__
 - __when the key is more than the middle element,we search in the right half__
 - __However,when the key is equal to the middle element,our search target is found and we return the index of the middle element.__



Let us update our code to reflect the above steps:


```js
const arr =  [0,5,12,23,34,35,46,47,58];
const binarySearch = (elements,value) => {
      let startIndex = 0;
      let endIndex = arr.length - 1;
      let middleIndex = Math.floor((startIndex + endIndex) / 2 );
      if (elements[middleIndex] === value) {
         return `Target value ${value} was found at index ${middleIndex}`;
         } else if (elements[middleIndex] < value) {
             startIndex = middleIndex + 1;
           } else {
              endIndex = middleIndex - 1;
         }     
 }
```
To keep going,you enclose the above steps in a loop which will stop when the lower(__startIndex__) boundary overtakes the upper(__endIndex__) one.This can easily be achieved by adding a while loop our code as below:

```js
const arr =  [0,5,12,23,34,35,46,47,58];
const binarySearch = (elements,value) => {
      let startIndex = 0;
      let endIndex = arr.length - 1;
      while (startIndex <= endIndex) { 
        let middleIndex = Math.floor((startIndex + endIndex) / 2 );
        if (elements[middleIndex] === value) {
             return `Target value ${value} was found at index ${middleIndex}`;
             } else if (elements[middleIndex] < value) {
                 startIndex = middleIndex + 1;
             } else {
                 endIndex = middleIndex - 1;
            }     
        }
 }
```
In other words,you can iterate as long as the lower boundary is below or equal to the upper one.Otherwise,there was no match found and the function returns __undefined__ implicitly(__lam returning a message informing the user that there was no match found in our array__). Our code should now look as below:

```js
'use strict'

const arr =  [0,5,12,23,34,35,46,47,58];

const binarySearch = (elements,value) => {
    let startIndex = 0;
    let endIndex = arr.length - 1;

    while (startIndex <= endIndex) {
        let middleIndex = Math.floor((startIndex + endIndex) / 2);
        if(elements[middleIndex] === value) {
            return `Target value ${value} was found at index ${middleIndex}`;
        }else if(elements[middleIndex] < value) {
            startIndex = middleIndex + 1;
        }else {
            endIndex = middleIndex - 1;
        }
     }
  return `Target value ${value} was not found in [${elements}]`;
}

console.log(`Result of binary search results: ${binarySearch(arr,35)}`);
```  

To ensure your array is always sorted,add the following code:

```js
let sortedArr = arr.sort((a,b) => {
        return a - b;
});
```

With this addition our code should look as below:


```js
'use strict'

const arr =  [0,5,12,23,34,35,46,47,58];

const binarySearch = (elements,value) => {
    let startIndex = 0;
    let endIndex = arr.length - 1;

    while (startIndex <= endIndex) {
        let middleIndex = Math.floor((startIndex + endIndex) / 2);
        if(elements[middleIndex] === value) {
            return `Target value ${value} was found at index ${middleIndex}`;
        }else if(elements[middleIndex] < value) {
            startIndex = middleIndex + 1;
        }else {
            endIndex = middleIndex - 1;
        }
     }
  return `Target value ${value} was not found in [${elements}]`;
}

let sortedArr = arr.sort((a,b) => {
        return a - b;
});

console.log(`Result of binary search results: ${binarySearch(sortedArr,35)}`);

```

### Sample iteration simulation from our binary search function
 
![Binary search simulation run](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qt213k16c8ee1569giiz.png)
 

### Where we can use binary search algorithm

Unlike other search algorithms, binary search can be used beyond just searching. For example, it allows for set membership testing, finding the largest or smallest value, finding the nearest neighbor of the target value, performing range queries, and more.


### The Efficiency of Binary Search

The time complexity of the Binary Search is __O(log2n)__, where __n is the number of elements__ in the array. This is far better compared to the __Linear Search__, which is of __time complexity O(n)__. Like many other search algorithms, Binary Search is an in-place algorithm. That means that it works directly on the original array without making any copies.

We have to keep in mind however, that __Binary Search only works on sorted arrays__. The sorting step itself, if using an efficient sorting algorithm, has a complexity of __O(nlogn)__. This means that in most cases, if the array is small, or if we need to search it only once, a __brute-force (e.g. Linear Search)__ algorithm might be better.

Given this, Binary Search really shines when we need to make repeated searches on large arrays. As previously mentioned, we needed __only 3 comparisons__ (comparisons being the most intensive tasks of all search algorithms), for my array of __8 elements__. However, if we had an array of __10,000,000 elements__, we would only need to check _24 elements, i.e. 0.0002%__ of the entire array.

### Conclusion

In this article, we have taken a look at Binary Search. It's simple, intuitive and efficient logic and implementation make it a very popular algorithm to demonstrate the divide-and-conquer strategy. Your feedback(s) are highly welcome and shall help me improve on this article or extend my understanding of algorithms.