Binary Search in JavaScript

What is Binary search in JavaScript?

In JavaScript, the binary search algorithm is a method utilized for locating elements and is based on the divide-and-conquer strategy. Using binary search, it becomes possible to find any specific item within a sorted array.

In JavaScript, the binary search algorithm works by repeatedly splitting the array in half until the desired element is located. With every iteration, it discards half of the elements that are left, leading to a much quicker search time when compared to a linear search approach.

In contrasting binary search with linear search, it is evident that binary search operates at a significantly faster pace. The time complexity associated with binary search is O(logN), while linear search executes with a time complexity of O(N).

In straightforward terms, it is a search method that employs a divide and conquer strategy, breaking down the issue into more manageable subproblems until they are reduced to a level where they can be solved directly. Binary search is an intuitive, easy-to-use, and effective searching algorithm.

Implementation of Binary search in JavaScript

Let's take an example:

Determine the position of "26" within the sorted array provided 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:

• ✅ 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.
• ✅ 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.
• ✅ 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.
• ✅ 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.
• ✅ 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.
• ✅ 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.
• ✅ 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

In JavaScript, binary search can be implemented using two distinct methods:

• ✅ Recursive method
• ✅ Iterative method

Recursive approach

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

Example

let recursiveFunction = function (arr, a , start, end) {
    // Base Condition
    if (start > end) return false;

    // Find the middle index
    let mid = Math.floor((start + end) / 2);

    // Compare mid with given key a
    if (arr[mid] === a) return true;

    // If Value at mid is greater than a,
    // search in the left half of mid
    if (arr[mid] > a)
        return recursiveFunction(arr, a, start, mid - 1);
    else

        // If Value at mid is smaller than a,
        // search in the right half of mid
        return recursiveFunction(arr, a,mid + 1, end);
}

// Driver code
let arr = [1, 3, 5, 7, 8, 9];
let a = 5;	
if (recursiveFunction(arr, a, 0, arr.length - 1)) {
    console.log("Value found!");
}
else { console.log("Value not found!"); }

a = 6;
if (recursiveFunction(arr, a, 0, arr.length - 1)) {
    console.log("Value found!");
}
else { console.log("Value not found!"); }

Output:

Value found!
Value not found!

Iterative approach

In this iterative method, we utilize a while loop rather than recursion, and this loop continues executing until it reaches the base condition, which occurs when the start value exceeds the end value.

Example

To illustrate the implementation of binary search through an iterative method, let us consider an example.

// Binary Search is implemented using an iterative function.
let iterativeFunction = function (sorted_arr, Value) {
  let start = 0,
     end = sorted_arr.length - 1;

  // Iterate as long as the beginning does not encounter the end.
  while (start <= end) {
     // find out the middle index
     let mid = Math.floor((start + end) / 2);

     // Return True if the element is present in the middle.
     if (sorted_arr[mid] == Value) return true;
     // Otherwise, look in the left or right half
     else if (sorted_arr[mid] < Value) start = mid + 1;
     else end = mid - 1;
  }

  return false;
};

// Driver code
let sorted_arr = [2, 6, 8, 10, 12, 14];
let Value = 9;

if (iterativeFunction(sorted_arr, Value, 0, sorted_arr.length - 1))
{
  console.log("Value found!");
}else{
  console.log("Value not found!");
} 
Value = 10;
if (iterativeFunction(sorted_arr, Value, 0, sorted_arr.length - 1)){
  console.log("Value found!");
}else{
  console.log("Value not found!")
}

Output:

Value not found!
Value found!

Time and space complexity of Binary search

In JavaScript, the binary search algorithm operates with a time complexity of O(logN), where N signifies the total count of elements or values contained within an array list.

However, in the context of comparing it with linear search, which possesses a time complexity of O(N), this highlights why binary search is significantly more efficient than linear search.

In JavaScript, the binary search algorithm executes all its operations on the original array itself; it does not generate a new array. Therefore, we can conclude that the space complexity of binary search is O(1).

In both scenarios, whether utilizing a recursive approach or an iterative one, the time complexity remains O(logN), while the auxiliary space required is 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, the binary search algorithm exhibits a time complexity of O(log n), rendering it highly effective for locating elements within extensive sorted arrays.

Simple Implementation

Implementing and comprehending binary search in JavaScript is quite straightforward.

Versatile

In JavaScript, the binary search algorithm is highly adaptable and can be utilized in numerous applications.

Reliable

Binary search is a dependable algorithm that guarantees the discovery of the target element, provided that it is present in the array.

Disadvantages of Binary search

Requires a sorted array

In JavaScript, the binary search algorithm is only applicable to arrays that have been sorted. In instances where the array is unsorted, it is essential to sort the array prior to implementing a binary search.

Not suitable for unsorted data

Binary search is ineffective for locating elements within unsorted data since it cannot efficiently identify the target item.

May not be the best choice for large arrays

When dealing with exceptionally large arrays, alternative search methods, including interpolation search or the use of hash tables, might offer greater efficiency.