Back To Tutorials

Javascript Binary Search Algorithm

Intermediatechallenge

In this challenge, you will implement the Binary Search algorithm in JavaScript. Binary search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing in half the portion of the list that could contain the item until you've narrowed the possible locations to just one.

Binary search operates in O(log n) time complexity, making it much faster than a linear search when dealing with large datasets.

Objective:

  • Implement a function that takes a sorted array and a target value, and returns the index of the target value in the array using the Binary Search algorithm.
  • If the target is not found, the function should return -1.

Requirements:

  1. Write a function binarySearch(arr, target) that:
    • Takes a sorted array and a target value.
    • Returns the index of the target value if found, or -1 if not found.
  2. Implement an iterative version of the binary search (you can optionally implement the recursive version as an extension).
  3. The function should be efficient with a time complexity of O(log n).

Steps:

  1. Setup:

    • Create an array of numbers that is sorted in ascending order.
    • Define a target number to search for in the array.

  2. Write the Function:

    • Define the binarySearch(arr, target) function.
    • Initialize two pointers, left and right, representing the range of array indices.
    • While the left pointer is less than or equal to the right pointer, calculate the middle index of the current range.
    • If the middle value matches the target, return the index.
    • If the middle value is less than the target, move the left pointer to mid + 1.
    • If the middle value is greater than the target, move the right pointer to mid - 1.
    • If the target is not found, return -1.

  3. Test the Function:

    • Run several tests with different sorted arrays and target values to ensure that the function works correctly.
    • Test cases should cover edge cases such as an empty array or an array with one element.

Resources:

Solution:

Here is a sample solution using an iterative approach to the binary search:

// JavaScript Binary Search Function
function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
      return mid; // Target found
    } else if (arr[mid] < target) {
      left = mid + 1; // Move to the right side of the array
    } else {
      right = mid - 1; // Move to the left side of the array
    }
  }

  return -1; // Target not found
}

// Example Usage
const sortedArray = [1, 2, 4, 5, 9, 12, 15, 22, 30, 31];
const target = 9;

const result = binarySearch(sortedArray, target);
console.log(result); // Output: 4 (index of 9 in the array)

Explanation:

  • binarySearch(): The function uses two pointers (left and right) to repeatedly narrow down the range of where the target value could be.

    • Mid Calculation: The middle of the current range is calculated, and then the algorithm checks whether the target is in the left or right half of the current range.

    • Edge Cases: If the array is empty or if the target is not present in the array, the function returns -1.

  • Time Complexity: The algorithm has a time complexity of O(log n), making it highly efficient for searching large sorted datasets.