Hey Guys,

DSA aka data structures is a big word for everyone. I am trying to make DSA simple and easy.
Here is first problem and my approach towards solution using python. This covers linear search and Binary search algorithms to reduce execution time.

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 returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Solution:

I have gone through question. I have list of the versions which are good or bad.

Step1: we need to go through list and find out the bad version. Whenever we want to go through list, we will use for loop. we need to consider first version and last version. we can use range type to generate versions. Okay?

Step2:

we have a function which determines the Version is good or bad. isBadVersion(version) gives true, if it a bad version or false for good version. Here comes if condition to check the version bad or not?

First Method:

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return an integer
# def isBadVersion(version):

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        for version in range(1,n+1):
            if isBadVersion(version):
                return version
        return n

I have submitted it and found that it is taking more time than expected. This is called linear search.

What to do?

Whenever you are looping through entire list and taking more time. we need to break down the list and loop. It is called binary search

Binary search:

Search a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

Binary search contains three variables i.e. indexes

• Left(Boundary)

• Mid

• Right(Boundary)

we need to find mid value every time to half the list. First we need to consider entire list and half it and goes with same step till we get empty.

In our problem,

• Left value is 1

• Right value is n

• Mid value should be

  (left+right)/2

we will evaluate the whether mid version is good or bad. if isBadVersion(mid) == False/Good version

Then, Search between mid and right next time, so left becomes mid+1.

if isBadVersion(mid) == True/Bad Version, Then Search between left and mid i.e. Right becomes mid

we repeat this exercise continuously until we get empty list or first bad version. This concludes that use of while loop till left value is less than right.

Let's start writing final solution

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        left=1
        right=n
        while (left<right): # Loop till left less than right value
             mid=(left+right)/2 #Finding out the mid value
             if isBadVersion(mid): # If the mid version is True/Bad
                 right=mid #Assigning Right Value to mid to search in right half of list
             else:
                  left=mid+1  #Assigning the left value to mid+1 to search in left half
        return int(left) #Return the first bad version

Credits: Leetcode GeekforGeeks