Phiên bản xấu đầu tiên trong Python

Trong một công ty, quản lý sản phẩm phát hiện phiên bản mới thất bại kiểm tra chất lượng. Mọi phiên bản sau phiên bản xấu đầu tiên đều xấu. Cho mảng A = [1,2,...n] và hàm isBadVersion(version_id). Tìm phiên bản xấu đầu tiên. Ví dụ: n=5, phiên bản 4 là xấu đầu tiên. isBadVersion(3)=false, isBadVersion(5)=true, isBadVersion(4)=true → kết quả 4.

Giải pháp

Sử dụng tìm kiếm nhị phân:

• Nếu n < 2 trả về n.
• Khởi tạo start=1, end=n.
• Trong khi start <= end: mid = (start+end)//2. Nếu isBadVersion(mid) và không isBadVersion(mid-1) → trả về mid. Ngược lại nếu isBadVersion(mid-1) → end=mid-1, else start=mid+1.

Ví dụ

Triển khai Python:

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)

Đầu vào

5 4

Đầu ra

4