পাইথনে ফার্স্ট ব্যাড ভার্সন

একটি কোম্পানিতে প্রোডাক্ট ভার্সন ১ থেকে n পর্যন্ত আছে। একটি ভার্সন ব্যাড হলে তার পরে সব ভার্সনও ব্যাড হবে। isBadVersion(version_id) ফাংশন দিয়ে যাচাই করা যায়। বাইনারি সার্চ ব্যবহার করে প্রথম ব্যাড ভার্সন বের করতে হবে।

সমাধানের পদ্ধতি

1. যদি n < 2 হয়, তবে n রিটার্ন করুন।
2. বাইনারি সার্চ: start = 1, end = n।
3. while start <= end:
   • mid = (start + end) // 2।
   • যদি isBadVersion(mid) সত্য এবং isBadVersion(mid-1) মিথ্যা হয়, তবে mid রিটার্ন করুন।
   • অন্যথায় যদি isBadVersion(mid-1) সত্য হয়, তবে end = mid - 1।
   • অন্যথায় start = mid + 1।

উদাহরণ কোড

first_bad = 0
def isBadVersion(version):
    if version >= first_bad:
        return True
    return False

class Solution:
    def firstBadVersion(self, n):
        if n < 2:
            return n
        start = 1
        end = n
        while start <= end:
            mid = (start + end) // 2
            if isBadVersion(mid) and not isBadVersion(mid - 1):
                return mid
            elif isBadVersion(mid - 1):
                end = mid - 1
            else:
                start = mid + 1

ob1 = Solution()
first_bad = 4
op = ob1.firstBadVersion(5)
print(op)

ইনপুট

5 4

আউটপুট

4