easy

First Bad Version

The First Bad Version algorithm is a classic problem in computer science, typically used to demonstrate the use of the binary search algorithm. The problem statement is as follows:

You have a series of versions of a software product, numbered from 1 to n. The versions are either good or bad, and you are given a function isBadVersion(version) that returns true if a given version is bad, and false otherwise. Your task is to find the first bad version of the software, i.e. the smallest version number such that isBadVersion(version) returns true.

Here's one possible solution to this problem in JavaScript:

function firstBadVersion(n) {
  let left = 1;
  let right = n;
 
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (isBadVersion(mid)) {
      right = mid;
    } else {
      left = mid + 1;
    }
  }
 
  return left;
}

This solution uses the binary search algorithm to iteratively narrow down the range of possible bad versions until it finds the first one. It maintains two pointers, left and right, that initially point to the first and last versions, respectively.

At each iteration of the loop, it computes the midpoint of the current range as mid, and checks whether isBadVersion(mid) returns true. If it does, it updates right to mid, since the first bad version must be in the left half of the range. Otherwise, it updates left to mid + 1, since the first bad version must be in the right half of the range. The loop terminates when left and right converge to the same version, which must be the first bad version.

The time complexity of this solution is O(log n), since the binary search algorithm divides the search space in half at each iteration. The space complexity is O(1), since the solution uses only a constant amount of additional memory to store the two pointers.