# The isBadVersion API is already defined for you. # @param version, an integer # @return a bool # def isBadVersion(version): class Solution(object): def firstBadVersion(self, n): """ :type n: int :rtype: int """ """ ex) 0 1 2 3 4 5 ^ use binary search O(log n) if x is corrupt and x-1 not corrupt, then xth is the first version move pointer to left half if x is corrupt move pointer to right half if x is not corrupt """ def helper(left, right): x = (left + right) / 2 # base case if x <= 0 or x == right: return x # check x is a bad vers and if previous vers is not currupted # x is the first corrupted vers. if isBadVersion(x) and not(isBadVersion(x-1)): return x if isBadVersion(x): return helper(left, x-1) else: return helper(x+1, right) return helper(1, n)
My binary search solution in Python with explanation
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.