Algorithms in Javascript: Binary Search Explained

As a full-stack developer, you know that efficiently searching for data is a critical part of many applications. One of the most powerful search algorithms every developer should master is binary search. Knowing when and how to apply binary search will level up your problem-solving skills and make you a more effective coder.

In this in-depth guide, we‘ll explore the binary search algorithm from multiple angles. You‘ll learn how binary search works, study different implementation approaches in JavaScript, see how its efficiency compares to other search methods, and discover its many practical applications. Let‘s dive in!

What is Binary Search?

Binary search is an efficient algorithm for finding the position of a target value within a sorted array. The key idea is to maintain a contiguous search space that contains the target and systematically reduce this space by comparing the middle element to the target value. Each comparison allows the search space to be halved, drastically reducing the number of remaining elements to search.

Here‘s a visualization of binary search in action:

With each comparison, the search space is divided in two. Binary search either finds the target value or reduces the search space to zero, confirming the target is not present.

Efficiency of Binary Search

Let‘s analyze the time complexity of binary search using a recurrence relation. The recurrence for binary search is:

T(n) = T(n/2) + O(1)

This means that the time to search an array of size n consists of the time to search half the array (T(n/2)) plus a constant amount of additional work (O(1)) to calculate the middle index and compare the element.

Solving this recurrence using the Master Method reveals that binary search runs in logarithmic time, O(log n). This is far more efficient than linear search, which requires O(n) time in the worst case.

To quantify this speedup, let‘s compare the maximum number of comparisons required to search an array of one billion elements:

Algorithm	Worst-case comparisons
Linear search	1,000,000,000
Binary search	30

That‘s right – binary search needs at most 30 comparisons to search one billion elements! Whenever you‘re searching a sorted array, using binary search is a no-brainer.

Implementing Binary Search in JavaScript

Now that you grasp how binary search works conceptually, let‘s implement it in code. We‘ll look at both iterative and recursive approaches.

Iterative Implementation

Here‘s an iterative implementation of binary search in JavaScript:

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    const guess = arr[mid];

    if (guess === target) {
      return mid;
    }
    if (guess < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return -1;
}

The key steps are:

1. Initialize two pointers, left and right, to the start and end of the array.
2. Enter a loop that continues as long as left is less than or equal to right.
3. Calculate the middle index mid using integer division.
4. Compare the middle element arr[mid] to the target value:
   • If they‘re equal, the target is found, so return mid.
   • If the middle element is less than the target, update left to search the right half of the array.
   • If the middle element is greater than the target, update right to search the left half of the array.
5. If the loop terminates without finding the target, return -1 to indicate the target is not present.

This implementation has O(log n) time complexity and O(1) space complexity since it iteratively halves the search space without allocating any extra memory.

Recursive Implementation

Here‘s a recursive implementation of binary search in JavaScript:

function binarySearch(arr, target, left = 0, right = arr.length - 1) {
  if (left > right) {
    return -1;
  }

  const mid = left + Math.floor((right - left) / 2);
  const guess = arr[mid];

  if (guess === target) {
    return mid;
  }
  if (guess < target) {
    return binarySearch(arr, target, mid + 1, right);
  }
  return binarySearch(arr, target, left, mid - 1);
}

The recursive approach follows the same logic as the iterative version, but it uses recursive calls to search the left or right half of the array. The base case returns -1 when left passes right, indicating the target is not found.

Recursion provides a more concise and expressive solution, but it incurs the overhead of function calls and consumes stack space proportional to the depth of recursion. In practice, the recursive implementation will be slightly slower than the iterative version due to this overhead.

Both iterative and recursive binary search have logarithmic time complexity, but the recursive version has O(log n) space complexity due to the implicit function call stack.

Variants of Binary Search

Beyond the basic binary search algorithm, there are a few common variants worth knowing.

Lower Bound and Upper Bound

When the array contains duplicate elements, you may want to find the first or last occurrence of a target value. The lower_bound and upper_bound variants of binary search handle these cases.

lower_bound returns the index of the first element that is not less than (i.e. greater than or equal to) the target value. upper_bound returns the index of the first element that is greater than the target value.

Here are the implementations in JavaScript:

function lowerBound(arr, target) {
  let left = 0;
  let right = arr.length;

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

    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return left;
}

function upperBound(arr, target) {
  let left = 0;
  let right = arr.length;

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

    if (arr[mid] <= target) {
      left = mid + 1;
    } else {
      right = mid;
    }
  }

  return left;
}

Using lower_bound and upper_bound, you can find the range of indices that contain a target value in a sorted array:

const arr = [1, 2, 3, 3, 3, 4, 5];
const target = 3;

const first = lowerBound(arr, target); // 2
const last = upperBound(arr, target) - 1; // 4

Binary Search in 2D Arrays

Binary search isn‘t limited to one-dimensional arrays. You can also apply binary search to efficiently search 2D arrays, as long as the array is sorted in a way that allows you to discard an entire half of the search space with each comparison.

For example, consider a 2D matrix where each row is sorted in ascending order and the first element of each row is greater than the last element of the previous row. Here‘s how you could apply binary search to find a target value in this matrix:

function binarySearch2D(matrix, target) {
  let top = 0;
  let bottom = matrix.length - 1;
  let numCol = matrix[0].length;

  while (top <= bottom) {
    const midRow = top + Math.floor((bottom - top) / 2);
    const lastElem = matrix[midRow][numCol - 1];

    if (lastElem === target) {
      return [midRow, numCol - 1];
    }
    if (lastElem < target) {
      top = midRow + 1;
    } else {
      const row = matrix[midRow];
      const col = binarySearch(row, target);

      if (col !== -1) {
        return [midRow, col]; 
      }
      bottom = midRow - 1;
    }
  }

  return [-1, -1];
}

This code first performs a binary search on the last element of each row to determine which row may contain the target. Then it performs a standard binary search within that row. This 2D version has a runtime of O(log m + log n), where m is the number of rows and n is the number of columns.

Applications of Binary Search

Binary search is a versatile algorithm with many practical applications. Let‘s look at a few examples.

Finding the Square Root

You can use binary search to efficiently find the square root of a number to a desired precision. The idea is to search for the square root in the range [0, number] by comparing the square of the middle value to the target number.

function squareRoot(number, precision = 0.001) {
  let left = 0;
  let right = number;

  while (right - left > precision) {
    const mid = left + (right - left) / 2;
    const square = mid * mid;

    if (square === number) {
      return mid;
    }
    if (square < number) {
      left = mid;
    } else {
      right = mid;
    }
  }

  return left;
}

This code continues the binary search until the search space is smaller than the desired precision. It returns an approximation of the square root that is within the specified tolerance.

Debugging a Linear Model

Imagine you have a buggy implementation of a linear model that‘s supposed to be monotonically increasing, but it produces a discontinuity at an unknown location. You can use binary search to efficiently pinpoint the location of the discontinuity.

function findDiscontinuity(model) {
  let left = 0;
  let right = 1;

  while (model(left) <= model(right)) {
    left = right;
    right *= 2;
  }

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

    if (model(left) <= model(mid)) {
      left = mid;
    } else {
      right = mid;
    }
  }

  return right;
}

This code first exponentially increases the search space until it contains the discontinuity. Then it performs a binary search to find the exact location of the discontinuity.

Solving the Game of Guess the Number

Binary search is the optimal strategy for the classic game of Guess the Number, where one player thinks of a number between 1 and n and the other player tries to guess it in the fewest attempts. By using binary search, the guesser can find the correct number in O(log n) guesses.

function guessNumber(n) {
  let left = 1;
  let right = n;

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

    if (res === 0) {
      return mid;
    }
    if (res < 0) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }

  return -1;
}

This code assumes a guess function that returns 0 if the guess is correct, -1 if it‘s too high, or 1 if it‘s too low. The binary search strategy guarantees finding the number in the optimal number of guesses.

Binary Search in the Real World

Binary search is a fundamental algorithm with widespread use in real-world systems. Many standard libraries provide built-in functions for binary search:

• C++ has std::binary_search and std::lower_bound in the <algorithm> header
• Java provides java.util.Arrays.binarySearch() and java.util.Collections.binarySearch()
• Python includes the bisect module with bisect_left and bisect_right functions

Database indexes often use binary search trees or B-trees, which are generalizations of binary search to tree-like data structures. These indexes enable fast O(log n) lookups for a given key.

Even everyday activities like looking up a contact in a phone book or finding a word in a dictionary use binary search. Anytime you have a sorted collection and need to efficiently locate an item, binary search is the way to go.

As Knuth famously stated, "Although the basic idea of binary search is comparatively straightforward, the details can be surprisingly tricky". By mastering binary search in all its variations, you‘ll be equipped to efficiently solve search problems in a wide range of domains.

Conclusion

In this comprehensive guide, we‘ve covered the fundamental concepts of binary search, from its underlying idea of reducing the search space to its many implementation variations and practical applications. We‘ve seen how binary search achieves a logarithmic time complexity, vastly outperforming linear search on sorted arrays.

To test your understanding, here are a few challenge problems:

1. Write a function that takes a sorted array of integers and a target integer and returns the range of indices that contains the target. Use the lower_bound and upper_bound functions.

2. Implement a function that takes a sorted 2D matrix and a target integer and returns the position of the target if it exists, or [-1, -1] if it doesn‘t. Each row of the matrix is sorted in ascending order, and the first integer of each row is greater than the last integer of the previous row.

3. Write an efficient algorithm to find the square root of a positive integer n with a precision of 0.001. Do not use any built-in square root functions.

4. You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad. Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad. You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

5. Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You must write an algorithm with O(log n) runtime complexity.

6. Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. Your algorithm‘s runtime complexity must be in the order of O(log n).

Remember, the key to mastering binary search is to practice implementing it in various scenarios and staying attentive to the tricky details. With a solid grasp of binary search, you‘ll be a more efficient and effective problem solver.

Happy searching!