Binary Search In JS

A Simple Binary Search In JS Example

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.

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

  1. Now first we will create a function as binarySearch() which accepts 2 parameters(list, item).
  2. After that, we will declare two variables that will store our low and high values.
  3. Then we start a while loop to begin our binary search action
  4. 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
  5. Initialize the array and the element to be found
  6. 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

CaseTime Complexity
Best CaseO(1)
Average CaseO(logn)
Worst CaseO(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.

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.