Binary Search Algorithm in JavaScript

Learn how to implement binary search - one of the most basic algorithms in computer science.
Published 2023-11-25 • 5 min read
Binary Search Algorithm in JavaScript

Binary search is a classic algorithm in computer science, known for its efficiency in searching sorted arrays. It’s a textbook example of a divide-and-conquer approach. Unlike linear search, which checks every element, binary search splits the array in half on each iteration. This significantly speeds up the search process.

However, it’s crucial to remember that binary search only works with sorted arrays. If an array isn’t sorted, you’ll need to sort it first before applying binary search. This requirement makes it particularly useful in scenarios where the data is already sorted or can be sorted efficiently.

In real life, especially in high-level languages like JavaScript, the usefulness of binary search is pretty limited, since it requires sorted array. Additionally, JavaScript’s standard library has a number of methods for searching and finding elements in arrays. But getting to grips with a few classic algorithms and understanding them really does make you a better developer in the long run. So, dive into this challenge head-on!

Understanding the Binary Search Process

Here’s a step-by-step breakdown of how binary search works:

  1. Find the Middle: Calculate the middle index of the array. This is done by averaging the start and end indices.

  2. Compare with Key:

    • If the element at the middle index equals the search key, return the index.
    • If the key is smaller than the middle element, focus on the left half of the array.
    • If the key is larger, focus on the right half.

  3. Repeat the Process: Keep repeating these steps on the chosen half. If you’re searching in the left half, the end index becomes the middle index minus one. If searching in the right half, the start index becomes the middle index plus one.

  4. Conclude the Search: Continue the process until the key is found or the sub-array size reduces to zero. If the key isn’t found, return -1.

This method effectively reduces the search space by half with each step, making it much faster than linear search, especially for large arrays.

Implementing Binary Search in JavaScript

Iterative Implementation

The iterative approach uses a while loop to divide the array and locate the key. Here’s the implementation:

const binarySearch = (sortedArray, key) => {
  // Initialize start and end indices
  let start = 0;
  let end = sortedArray.length - 1;

  // Continue the loop until start index is less than or equal to end index
  while (start <= end) {
    // Calculate the middle index of the current sub-array
    let middle = Math.floor((start + end) / 2);

    // Check if the middle element is the key
    if (sortedArray[middle] === key) {
      return middle; // Key found, return its index
    } else if (sortedArray[middle] < key) {
      start = middle + 1; // Key is in the right sub-array
    } else {
      end = middle - 1; // Key is in the left sub-array
    }
  }
  return -1; // Key not found in the array
};

Recursive Implementation

The recursive version calls itself with updated bounds based on the comparison:

const binarySearchRecursive = (array, key, start, end) => {
  // Base case: if start index exceeds end index, key is not present
  if (start > end) return -1;

  // Calculate the middle index
  let mid = Math.floor((start + end) / 2);

  // If the middle element is the key, return its index
  if (array[mid] === key) return mid;

  // If the key is less than the mid element, search in the left sub-array
  if (array[mid] > key)
    return binarySearchRecursive(array, key, start, mid - 1);
  // If the key is greater than the mid element, search in the right sub-array
  else return binarySearchRecursive(array, key, mid + 1, end);
};

Efficiency and Complexity

Time Complexity

  • Best Case (O(1)): Occurs when the target value is at the middle of the array. The search ends in a single step.
  • Worst Case (O(log n)): Happens when the target is at the start or end of the array, requiring the maximum number of steps.
  • Average Case (O(log n)): On average, the complexity remains logarithmic, making binary search efficient for large arrays.

Space Complexity

  • Iterative Approach (O(1)): Uses a fixed amount of space, irrespective of the array size.
  • Recursive Approach (O(log n)): Involves additional space for the call stack, proportional to the depth of the recursive calls.

Both implementations highlight binary search’s efficiency, especially in large datasets where reducing the search space with each step significantly cuts down on the time and resources needed.

Binary search isn’t just a theoretical concept; it has practical applications in everyday software development:

  1. Searching in Databases: Often used in database algorithms to quickly locate records, this is the basic algorithm behind database indexing.
  2. Optimizing Performance: In scenarios where data is mostly static but frequently searched, binary search dramatically improves performance.
  3. Algorithmic Foundations: It serves as a foundation for more complex algorithms like binary search trees.
  4. File Processing: Efficient for searching in sorted files, particularly large ones.
  5. git bisect: This tool helps you find commit that introduced a bug, it’s just a binary search.

Conclusion

Binary search is a cornerstone of efficient searching in computer science. Particularly in JavaScript, its implementation is straightforward, yet it offers significant performance benefits over linear search, especially with large datasets.

The algorithm itself is nothing special, as I said we have more efficient ways to find stuff in most cases. But this idea can be used in many real-life scenarios. The key is to understand it and know that it’s there and use it when necessary.

#javascript