Binary Search in JavaScript

What is Binary search in JavaScript?

In JavaScript, binary search is a technique that is used for searching and works on the divide-and-conquer approach. With the help of binary search, we can search for any element in a sorted array.

In JavaScript, binary search divides the array into half until the element is found. With each repetition, it eliminates half of the remaining elements, which results in a significantly faster search time compared to linear search.

When we compare binary search with the linear search, it is much faster, and the complexity of binary search is O(logN), whereas linear search works in O(N) time complexity.

In simple words, it is a searching technique that uses the divide and conquer approach that divide the problem into simpler problems until it becomes simple enough to solve them directly. Binary search is a simple, user-friendly, and efficient search algorithm.

Implementation of Binary search in JavaScript

Let's take an example:

Find out the index of "26" out of a sorted array that is given below.

[ 2, 6, 10, 14, 18, 22, 26, 30, 34]

Let's see the step-by-step process to apply binary search in the above example:

1. First, to perform a binary search, we need to keep track of three variables: startIndex, middleIndex, and endIndex. Let startIndex = 0. endIndex can always be calculated with the help of an array. endIndex = arr.length - 1 where length: endIndex = arr.length - 1.
2. With the use of startIndex and endIndex and divide them by 2 we will get an initial middleIndex. We can round down or up with Math.floor() or Math.ceil(), but we'll round down with Math.floor() in this case: let middleIndex = Math.floor((startIndex + endIndex)/2) within our while loop, this will be the only index variable we store. The process will then be replaced until the while loop is terminated. While (startIndex >= endIndex) is used in our case.
3. Now, let's take a look at the array; we have a total of 9 elements. We divide by two and use Math.floor() to round down, which selects a middleIndex at Index 4, where we found the number 18. Now, we will compare the number 18 to our target number, which is 26, to see which one is greater than the other.
4. We know that our target value will be somewhere to the right of the middleIndex if the middleIndex value is less than 26. The current middleIndex value will be assigned to our startIndex variable, effectively removing the left half of the array.
5. We know that our target value will be somewhere left side of the middleIndex if the middleIndex value is greater than the target value of 26. The endIndex variable can then be set to the current middleIndex value, effectively removing the right half of the array.
6. Now, we will check if the middleIndex is equal to the target value, which is 26. It will depend on the size of your array and your target number, and the loop may only loop once or dozens of times.
7. We found our target number, which is 26, because the middleIndex number value is equal to our target number. Finally, we have completed our binary search.

Types of approaches in Binary search

There are two ways/approach to do binary search in JavaScript:

• Recursive approach
• Iterative approach

Recursive approach

1. The base condition of the recursive approach is, if the starting index is greater than the ending index, return false.
2. Now, compute the middle index.
3. Then, compare the middle element with the number a. If it is equal to a, return true.
4. If it is greater, call the same functions with the ending index = middle-1 and repeat step 1.
5. If it is smaller, call the same function with starting index = middle +1 and repeat step 1.

Example

Output:

 Value found! Value not found! 

Iterative approach

In this iterative approach, instead of recursion, we use the while loop, and the loop runs until it hits the base condition, i.e. start becomes greater than the end.

Example

Let's take an example to understand the implementation of binary search using an iterative approach.

Output:

 Value not found! Value found! 

Time and space complexity of Binary search

Binary search in JavaScript has a time complexity of O(logN); here, N is nothing but the number of elements or values that are present there in an array list.

But when it comes to the comparison with the linear search, which has a time complexity of O(N), that is why binary search is far better than linear search.

In JavaScript, binary search performs all the operations over that same original array; it doesn't create the new array, so we can say that binary search works in O(1) space.

In both of the cases, the recursive and iterative one, the Time complexity will be O(logN), and the Auxiliary space will be O(1).

Application of Binary search

• Searching: In JavaScript, binary search is used to find an element in a sorted array efficiently.
• Database queries: It is used to locate records in a database table quickly this is sorted by a specific key.
• Finding the closet match: Binary search can be used to find the closest value to a target value in a sorted list.
• Interpolation search: In JavaScript, binary search can be used as a starting point for interpolation search, which is an even faster search algorithm.

Advantages of Binary search

Efficient

In JavaScript, binary search has a time complexity of O(log n), which makes it very efficient for searching large sorted arrays.

Simple Implementation

Binary search in JavaScript is relatively easy to implement and understand.

Versatile

In JavaScript, binary search is very versatile, and it can be used in a wide variety of applications.

Reliable

Binary search can be a reliable algorithm that will always find the target element if it exists in the array.

Disadvantages of Binary search

Requires a sorted array

In JavaScript, binary search only works on sorted arrays. If the array is not sorted, it must be sorted before binary search can be used.

Not suitable for unsorted data

Binary search is not suitable for searching in unsorted data as it will not be able to find the target element efficiently.

May not be the best choice for large arrays

For very large arrays, other search algorithms, such as interpolation search or hash tables, may be more efficient.