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
6int firstBadVersion(int n) {
7 int left = 1, right = n;
8 while (left < right) {
9 int mid = left + (right - left) / 2;
10 if (isBadVersion(mid)) right = mid;
11 else left = mid + 1;
12 }
13 return left;
14}The code above implements the binary search algorithm. It initializes two pointers, left and right, to perform the search. If isBadVersion(mid) is true, the first bad version must be at mid or to its left, hence right is adjusted. Otherwise, the bad version must be to the right of mid, hence left is adjusted. The loop continues until left meets right, at which point the first bad version is identified.
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
1public class Solution : VersionControl {
private 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;
}
public int FirstBadVersion(int n) {
return BinarySearch(1, n);
}
}The C# code implements a recursive BinarySearch to determine the first bad version. Adjusting the search range at each recursive step helps in pinpointing the sought version efficiently as the stack unwinds.