In this tutorial, we are going to learn about **Binary Search In JS**. We will take look at what is Binary Search and how to implement this algorithm on our own. Also, we will take a look at its various aspects as well like its Run-time complexity and space-time complexity. Binary Search is basically a search algorithm that helps you find out the elements you search for. Unlike Linear Search, which loops through each individual item one by one and yields the result. Whereas, Binary Search Algorithm divides the given items into two equal halves and starts searching for them in each half. We will look through our binary search in js program a bit later in this tutorial. For now, let us understand the concepts encircling the Binary Search Algorithm.

Table of Contents

#### What is Binary Search Algorithm?

In general Computer Science terms, a Binary Search, or a half-interval linear search, or a logarithmic search is a searching algorithm. This searching algorithm helps us find the value and the position of an item in a given sorted array. Binary search compares the target value to the middle element of the array. The item is compared with the middle element in the list using the divide and conquer strategy, which is used in binary search. In any other case, depending on the outcome of the match, we search into either half. The goal of binary search is to split the issue set in half repeatedly until you get the solution. The strategy benefits from the sorted data collection. This is crucial because the binary search cannot find elements in a collection that have not been sorted. The algorithm is described in the following pseudocode:

var searchValue = 1199 index = midpoint of current array if searchValue == value at index return index if searchValue > value at index do binary search of upper half of array if searchValue < value at index do binary search of lower half of array

Since this approach always breaks the problem in half, the runtime is actuallyÂ **O(log(n))**, which is significantly faster thanÂ **O(n)**Â for a large data set.

#### Approach 1: Binary Search In JS Iterative Way

- Now first we will create a function as binarySearch() which accepts 2 parameters(list, item).
- After that, we will declare two variables that will store our low and high values.
- Then we start a while loop to begin our binary search action
- mid = (low + high)/2Â if (a == arr[mid])Â return midÂ else if (a > arr[mid]) // a is on the right sideÂ low = mid + 1Â else // a is on the left sideÂ high = mid – 1
- Initialize the array and the element to be found
- Print the resulting position if the element is found else print Not found.

const binarySearch = (list, item) => { let low = 0 let high = list.length - 1 while (low <= high) { const mid = Math.floor((low + high) / 2) const guess = list[mid] if (guess === item) { return mid } if (guess > item) { high = mid - 1 } else { low = mid + 1 } } return null //if not found } console.log(binarySearch([1, 2, 3, 4, 5], 1)) //0 console.log(binarySearch([1, 2, 3, 4, 5], 5)) //4 console.log(binarySearch([1, 2, 3, 4, 5], 6)) //null

#### Time Complexity

Case | Time Complexity |
---|---|

Best Case | O(1) |

Average Case | O(logn) |

Worst Case | O(long) |

**Best Case Complexity** – In a binary search, the best case scenario is when the searchable element is discovered in the first comparison, or when the first middle element is in fact the searchable element. Binary search has a best-case temporal complexity of O. (1).

**Average Case Complexity** – For a binary search, the average case time complexity is O. (logn).

**Worst Case Complexity**: The worst-case scenario for binary search is when we have to continue narrowing the search space until there is just one element. Binary search has a worst-case temporal complexity of O. (long).

## Approach 2: Binary Search In JS Using Recursive Function

Recursive Method:

- BASE CONDITION: Return false if the starting index exceeds the ending index.
- Calculate the median index.
- The center element is to be compared to x. Return true if equal.
- If bigger, repeat step 1 and call the same method with an ending index of middle-1.
- If smaller, repeat step 1 and call the same function with a starting index of middle+1.

The JavaScript code for the Binary Search (Recursive Approach) is shown below:

let recursiveFunction = function (arr, x, 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 x if (arr[mid]===x) return true; // If element at mid is greater than x, // search in the left half of mid if(arr[mid] > x) return recursiveFunction(arr, x, start, mid-1); else // If element at mid is smaller than x, // search in the right half of mid return recursiveFunction(arr, x, mid+1, end); } // Driver code let arr = [1, 3, 5, 7, 8, 9]; let x = 5; if (recursiveFunction(arr, x, 0, arr.length-1)) console.log("Element found"); else console.log("Element not found"); x = 6; if (recursiveFunction(arr, x, 0, arr.length-1)) console.log("Element found"); else console.log("Element not found");

## Conclusion

This is it for this tutorial folks. Hope this simple program may have cleared some of your doubts. This simple binary search in js program for example may help you in understanding the fundamentals of binary searching algorithms. This is just a mere solution for a binary search program. There are many more complex programs that we can build with this searching method.