Binary Search in JavaScript

Binary Search in JavaScript

In this article, you will learn how to implement binary search in javascript both by recursively and iteratively

Welcome back, guys!! This is the 2nd blog in my "Competitive Programming using the JavaScript" series. where I share my learning with you, which I have learned while starting out with CP in JavaScript. So, Let's get started!

Today in this blog I will be explaining to you: What Binary Search is, how does it work, and how it is implemented in JavaScript.

What is Binary Search?

It is one of the most efficient and fast searching algorithms which gives us our answers in a very little amount of time in comparison to linear search. The binary search takes O(log n) time to search an element. On the other hand, the linear search takes O( n ) time.

binary-and-linear-search-animations.gif

One Important point to remember is that binary search only works if your search space is sorted or it's monotonic ( i.e. value is either non-decreasing or non-increasing). If your array is not already sorted, then you need to sort it first with the sorting algorithm.

The binary search uses a divide and conquer approach. It's working we will discuss it next.

How does binary search works?

As mentioned earlier, we will need a sorted data set of n number of elements.

  • First, we start with taking the start index and end index
  • Secondly, we take the mid element and compare it with the element we need to find. If it matches then we return the index.
  • if the mid element is less than the key element, It means our key element is present after the mid index. So, we search the element from mid+1 to end index.
  • if the mid element is more than the key element, It means our key element is present before the mid index, So, we search the element from start to mid index.
  • We repeat this until the element is found, otherwise return -1.

Implementaion in Javascript

The two most common ways to implement binary search are:

  1. Binary search recursively

  2. Binary search iteratively

1. Implementing binary search recursively

const binarySearch = (arr, key, start= 0, end= arr.length - 1) => {

  //Search if the array exists
  if(start<= end){
      //Get the mid
      const mid = Math.ceil((start+ end) / 2);

      //If element found
      //Return its index
      if(key === arr[mid]){
        return mid;
      }

      //If value is less 
      //Then search in the lower range
      if(key< arr[mid]){
        return binarySearch(arr, key, start, mid - 1);
      }else{
        //Else search in greater range
        return binarySearch(arr, key, mid + 1, end);
      }
  }

  //If not found then return -1
  return -1;
}

Test

const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log(binarySearch(arr, 9));
console.log(binarySearch(arr, 15));

Output:
 8 // Element 9 is found at 9th postion, so we get the index 8
-1 // Element 15 doesn't exist in the array so we get -1

Time Complexity: O( log n ) Space Complexity: O( n )

How fast is binary search is?

Let's suppose we have an array with 1,00,000 elements. In the worst case, It would take linear search 1,00,000 operations to as its time complexity is O( n ) While on the other hand, the binary search would take only 17 operations in the worst case. If you calculate log2(100000) = 16.60. Hence, we can get an idea of how fast binary search is in comparison to linear search.

2. Implementing binary search iteratively

const binarySearch = (arr, key) => {
  //set start and low indexes
  let start = 0;
  let end= arr.length - 1;

  //Loop till there elements needs to be searched in collection
  while(start <= end){
    //Get the mid
    let mid = Math.ceil((start+ end) / 2);

    //If found return the index
    if(arr[mid] === key){
       return mid;
    }

    //If value is less
    //Then search in lower range
    if(key < arr[mid]){
      end = mid - 1;
    }else{
      //Else search in upper range
      start= mid + 1;
    }
  }

  //If not found return -1
  return -1;
}

Test

const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log(binarySearch(arr, 9));
console.log(binarySearch(arr, 15));

Output:
 8 // Element 9 is found at 9th position, so we get the index 8
-1 // Element 15 doesn't exist in the array so we get -1

Time Complexity: O( log n )

Whereas there won't be any copy of array needs to be created so the space will stay constant

Space Complexity: O(1).

Conclusion

You must have a good idea about Binary Search Algorithm, It's a really fast searching algorithm than the linear search when we have a sorted array with time complexity of O( log n ).

I hope I've made it easy for you to understand. I really appreciate any feedback or topic request in the Competitive Programming using Javascript series or any other web-related topics that you want me to write about :)

Thanks for reading, If you liked it Please give it a like or tell me in the comments. Happy Coding!!