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#include <stdbool.h>
2
3// Forward declaration of isBadVersion API.
4bool isBadVersion(int version);
5
6class Solution {
7public:
8 int firstBadVersion(int n) {
9 int left = 1, right = n;
10 while (left < right) {
11 int mid = left + (right - left) / 2;
12 if (isBadVersion(mid)) right = mid;
13 else left = mid + 1;
14 }
15 return left;
16 }
17};The solution is similar to the one in C, utilizing binary search to narrow down the possibilities for the first bad version by adjusting the left and right pointers based on the result of isBadVersion at mid. Once left and right converge, the first bad version is found.
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/**
In the JavaScript solution, a recursive binarySearch function is utilized. The recursive breakdown persistently intensifies focus around the midpoint analysis until the original function invocation recovers the earliest defective version from the closed search range.