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 else: start = middle + 1 if isBadVersion(middle): return middle else: 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 🙂