First Bad Version

Problem: First Bad Version

We use binary search to find the first bad version. We use two pointers to allocate operating sub-array and care about the middle element. If the first pointer points to a bad version, then it's definitely the first bad version. Otherwise, if the middle pointer points to a bad version, the first bad version is surely between the first pointer and the middle pointer. If the middle pointer points to a good version while the last pointer points to a bad version, then the first bad version is in the right half.

Code in Python:

# 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
        """
        i, j = 1, n
        while i < j:
            if isBadVersion(i): return i
            if isBadVersion((i+j)/2):
                i += 1
                j = (i+j)/2
            else:
                i = (i+j)/2+1
        return i