# 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 = 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 Searchis a searching algorithm used in a sorted array byrepeatedly 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:**

- 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;

- Iterative Method
- Recursive Method

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

- 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

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