Sponsored
Sponsored
This approach uses the concept of binary search to efficiently find the first bad version by minimizing the number of calls made to the given isBadVersion API. By leveraging binary search, we can reduce the problem set size by half with each iteration, therefore achieving O(log n) time complexity.
Time Complexity: O(log n)
Space Complexity: O(1)
1/**
2 * Definition for isBadVersion()
3 *
4 * @param {integer} version number
5 * @return {boolean} whether the version is bad
6 * isBadVersion = function(version) {
7 * ...
8 * };
9 */
10
11/**
12 * @param {function} isBadVersion()
13 * @return {function}
14 */
15var solution = function(isBadVersion) {
16 /**
17 * @param {integer} n Total versions
18 * @return {integer} The first bad version
19 */
20 return function(n) {
21 let left = 1, right = n;
22 while (left < right) {
23 let mid = Math.floor(left + (right - left) / 2);
24 if (isBadVersion(mid)) {
25 right = mid;
26 } else {
27 left = mid + 1;
28 }
29 }
30 return left;
31 };
32};The JavaScript version adheres to the binary search approach. With each iteration, it checks whether the middle point indicates a bad version, adjusting the search range respectively till left pinpoint the first bad version.
This approach explores a recursive implementation of the binary search technique to identify the first bad version. Employing recursion allows the continual division of the search problem into smaller subproblems until the solution is found.
Time Complexity: O(log n)
Space Complexity: O(log n) - due to recursion stack
1#include <stdbool.h>
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
int binarySearch(int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
if (isBadVersion(mid)) return binarySearch(left, mid);
else return binarySearch(mid + 1, right);
}
return left;
}
class Solution {
public:
int firstBadVersion(int n) {
return binarySearch(1, n);
}
};The solution takes advantage of C++'s support for recursive functions to spot the first bad version through binarySearch. With each recursive call, it assesses the midpoint and adjusts the search range, seeking to locate the first bad version.