First bad Version

Problem description:

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.


This is solved using binary search since we can see the list of versions as an array of 0’s and 1’s in sorted order having zeroes as good versions and ones as bad versions, so our task is to find the first occurrence of 1, so how can we find the first occurrence of a number on a sorted array?… Binary search!!
So we basically…

1.- Create to pointers, one pointing to the beginning of the list (start = 0) and another one to the end of the list (end = n)
1.- Check if the middle element (middle = start + end / 2) is a correct version
2.- If it is a correct version we now know we don’t need the second half of the list so we go left (end = middle-1), otherwise we go right (start = middle+1)
3.- Repeat steps 1 and 2 until there is no more elements to check (while start <= end)

    def firstBadVersion(self, n):
        start = 1
        end = n
        middle = 0
        while(start <= end):
            middle = (start + end) / 2
            if isBadVersion(middle):
                end = middle - 1
                start = middle + 1
        if isBadVersion(middle):
            return middle
            return middle + 1

Runtime complexity: O(log n) since we cut the array in half at every step, so for an array of size 10 we just need log(10) = 3 operations to find the first bad version šŸ™‚


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s