```
# 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)
```