Binary Search Algorithm and Implementation in JavaScript

Photo by Markus Spiske on Unsplash

Binary Search algorithm is used to find the index of a given element in a sorted array.

Lets see the following example:

Input: arr[] = {10, 20, 30, 50, 60, 80, 110, 130, 140, 170}
x = 110
Output: 6
Explanation: Element x is present at index 6. 

Are there any other approach instead of Binary Search?

Linear Search is another method to find the given value in an array. It will traverse through the array element by element and search whether the element is exist in the array or not. The time complexity of Linear Search is O(n). We will look at the Time Complexity in future article.

Binary Search is a searching algorithm used in a sorted array by repeatedly dividing the search interval in half. The time complexity of Binary Search is O(Log n).

Following are the basic steps to perform Binary Search:

1. the array needs to be in sorted order

2. set the Low Index -> First element of array and High Index -> Last element of array

3. Set Middle Index -> average of low and high indexes (Low + High)/2

4. If element at Middle index is the target value then return the middle index

5. If target element is less than element at Middle index, set the High Index -> (Middle Index-1)

6. If target element is greater than element at Middle index, set the Low Index -> (Middle Index+1)

7. Repeat the steps from 3–6 until we get the index value or if the element is not exist then we have to return -1.

There are 2 ways to perform Binary Search;

1. Iterative Method
2. Recursive Method

You may wonder what these 2 ways are. Lets look at it in depth.

1. Iterative Method follows Decrease and Conquer approach, where for each iteration the size of the input data is reduced and then the solution process is processed.

Following is the pseudocode for Iterative method:

  binarySearch(arr, target, low, high)
        // here we will calculte the low and high values
        repeat till low <= high
               mid = (low + high)/2
                   if (target == arr[mid])
                   return mid
   
                   else if (target > arr[mid]) // targetis on the right side
                       low = mid + 1
   
                   else                  // targetis on the left side
                       high = mid - 1

2. Recursive Method follows Divide and Conquer approach, where the input data is divided into sub-problems and then the process will be processed towards finding solution.

Following is the pseudocode for Recursive method:

    binarySearch(arr, target, low, high)
           if low > high
               return False 
   
           else
               mid = (low + high) / 2 
               if target== arr[mid]
                   return mid
       
               else if target> arr[mid]        // target is on the right side
                   return binarySearch(arr, target, mid + 1, high)
               
               else                        // targetis on the left side
                   return binarySearch(arr, target, low, mid - 1) 

Now lets see the JavaScript implementations for both methods

1. Iterative Method:

function binarySearch(arr, target) {
  let low= 0;
  let high = arr.length - 1;

  while (low <= high) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return -1; // if target not found
}

// Example usage:
const arr = [1, 3, 4, 6, 7, 8, 9];
const target = 4;
const index = binarySearch(arr, target); // returns 2

The iteration should be stopped when the low index is surpasses or higher than the high index.

2. Recursive Method:

function binarySearch(arr, l, r, x){
 if (r >= l) {
  let mid = l + Math.floor((r - l) / 2);

  // If the element is present at the middle
  // itself
  if (arr[mid] == x)
   return mid;

  // If element is smaller than mid, then
  // it can only be present in left subarray
  if (arr[mid] > x)
   return binarySearch(arr, l, mid - 1, x);

  // Else the element can only be present
  // in right subarray
  return binarySearch(arr, mid + 1, r, x);
 }

 // We reach here when element is not
 // present in array
 return -1;
}

let arr = [ 2, 3, 4, 10, 40 ];
let x = 10;
let n = arr.length
let index = binarySearch(arr, 0, n - 1, x);

That’s all.. hope you enjoyed it.