How to: Implement Binary Search in Javascript

Binary search is a powerful algorithm used to search for an element in a sorted array. It is one of the most efficient search algorithms, with a time complexity of O(log n). In this blog post, we will explore how to implement binary search in Javascript.

What is Binary Search?

Binary search is a search algorithm used to find the position of a specific element in a sorted array. The algorithm works by repeatedly dividing the search interval in half. At each step, the algorithm compares the middle element of the interval with the target element. If the middle element is equal to the target element, the search is successful. Otherwise, the algorithm narrows down the search interval and repeats the process until the target element is found or the search interval is empty.

Implementing Binary Search in Javascript

To implement binary search in Javascript, we need to define a function that takes an array and a target element as input and returns the index of the target element in the array. Here’s an example code snippet that implements binary search in Javascript:

function binarySearch(array, target) {
  let left = 0;
  let right = array.length - 1;
  
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (array[mid] === target) {
      return mid;
    } else if (array[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  
  return -1;
}

Let’s break down the code. First, we define a function called binarySearch that takes an array and a target element as input. We initialize two variables left and right to represent the left and right endpoints of the search interval, respectively. We set left to 0 and right to the index of the last element in the array.

Next, we enter a while loop that continues until the search interval is empty (left > right). At each iteration of the loop, we calculate the index of the middle element of the search interval using the formula (left + right) / 2. We use the Math.floor function to ensure that the result is an integer.

We then compare the middle element with the target element. If they are equal, we have found the target element and we return its index. If the middle element is less than the target element, we know that the target element must be in the right half of the search interval, so we update left to be mid + 1. If the middle element is greater than the target element, we know that the target element must be in the left half of the search interval, so we update right to be mid - 1.

If the target element is not found after the while loop, we return -1 to indicate that the element is not in the array.

Using the Binary Search Function

Now that we have defined the binary search function, let’s see how we can use it to search for an element in an array. Here’s an example code snippet:

const arr = [1, 3, 5, 7, 9];
const target = 5;
const index = binarySearch(arr, target);
console.log(index); // Output: 2

In this example, we have an array arr that is already sorted in ascending order. We want to find the index of the element target, which is 5. We call the binarySearch function with arr and target as input, and store the result in the variable index. Finally, we print the value of index to the console, which should be 2 since 5 is located at index 2 in the array.

Conclusion

In this blog post, we explored how to implement binary search in Javascript. We learned that binary search is a powerful algorithm used to search for an element in a sorted array, with a time complexity of O(log n). We also saw how to handle edge cases when implementing binary search in Javascript.

Remember to always test your code thoroughly and handle edge cases properly to ensure that your code works correctly in all scenarios. Happy coding!