Find first bad version (part 2)

Question

This is new code based on some new ideas to reduce calls to is_bad_version. Refer to the previous version of the code discussion from here.

Any smarter ideas for better time complexity, any code bug or code style advice are highly appreciated. My major idea is divide and conquer like a binary search/quick select.

Problem:

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad. Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad. You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Source code:

def is_bad_version(number):
    if number == 0:
        return False
    else:
        return True


def find_first_bad_index(numbers):
    start = 0
    end = len(numbers) - 1
    if start == end:
        if is_bad_version(numbers[start]):
            return start
        else:
            raise Exception('all good!')
    while start < end:
        mid = start + (end - start) / 2
        if is_bad_version(numbers[mid]):
            end = mid
        else:
            start = mid + 1
    if start == end:
        if is_bad_version(numbers[start]):
            return start
        else:
            raise Exception('all good!')

if __name__ == "__main__":
    print find_first_bad_index([0,0,0,1,1,1,1,1])
    print find_first_bad_index([0,0,0,0,0,0,0,1])

Answer 1

Document your code in the code. If trying to stick to all pertaining PEPs gets too much, have a look at Code Documentation Advice.

If you don't want to go with bisect
(noteworthy simplifications/improvements (esp. over/of VersionWrap), anyone? Please edit.)

from bisect import bisect
from functools import total_ordering


class NoBadVersion(Exception):
    """Home brewed exception to diferentiate from other
    kind of exceptions and avoid too generic except clauses.
    """


@total_ordering
class VersionWrap:
    """Support version designator comparison"""
    __slots__ = 'version', 'bad'
    def __init__(self, v, b = None):
        self.version = v
        self.bad = b
    def is_bad(self):
        if self.bad is None:
            self.bad = is_bad_version(self.version)
        return self.bad
    def __eq__(self, other):
        return other.is_bad() == self.is_bad()
    def __lt__(self, other):
        return not self.is_bad() and other.is_bad()


def find_first_bad_index(numbers):
    """Find the first bad version

    Assumes is_bad_version(numbers[i]) implies
     is_bad_version(numbers[i+n]) for every natural number n.
    numbers is a sequence of version designators,
    suitable as parameters to is_bad_version().

    Returns the lowest b such that is_bad_version(numbers[b])
    """
    firstNonGood = bisect([VersionWrap(vd) for vd in numbers],
                          VersionWrap(None, False))
    if firstNonGood == len(numbers):
        raise NoBadVersion('none bad!')

    return firstNonGood

, stay with

"""Find the first bad version

Keep number of calls to is_bad_version() at minimum.
"""


class NoBadVersion(Exception):
    """Home brewed exception to diferentiate from other
    kind of exceptions and avoid too generic except clauses.
    """


def is_bad_version(number):
    """dummy for an external predicate costly to evaluate"""
    return number


def find_first_bad_index(numbers):
    """Find the index of the first bad version

    Assumes is_bad_version(numbers[i]) implies
    is_bad_version(numbers[i+n]) for every natural number n.
    numbers is a sequence of version designators,
    suitable as parameters to is_bad_version().

    Returns the lowest b such that is_bad_version(numbers[b])
    """
    start = 0
    end = len(numbers)

    while start < end:
        mid = start + (end - start) // 2
        if is_bad_version(numbers[mid]):
            end = mid
        else:
            start = mid + 1

    if start == len(numbers):
        raise NoBadVersion('none bad!')
    return start


if __name__ == "__main__":
    numbers = [1] * 7
    for good in range(len(numbers)+1):
        print(find_first_bad_index(numbers))
        numbers[good] = 0