# Binary Search Algorithm and Implementation in JavaScript

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 = 110Output: 6Explanation: 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.lengthlet index = binarySearch(arr, 0, n - 1, x);`

That’s all.. hope you enjoyed it.