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

Giả sử trong một công ty, một giám đốc sản phẩm đang lãnh đạo một nhóm phát triển một sản phẩm mới. Giả sử phiên bản mới nhất không kiểm tra được chất lượng. Vì mỗi phiên bản đều được phát triển dựa trên phiên bản trước nên tất cả các phiên bản sau một phiên bản xấu đều sẽ xấu. Vì vậy, chúng ta có một mảng A với n phần tử [1, 2,… n] và chúng ta phải tìm phiên bản xấu đầu tiên từ mảng này.

Hãy xem xét chúng ta có một hàm isBadVersion (version_id), hàm này sẽ trả về việc phiên bản đó có xấu hay không. Ví dụ:giả sử n =5 và phiên bản =4 là phiên bản xấu đầu tiên. Vì vậy, nếu isBadVersion (3) trả về false isBadVersion (5) trả về true và isBadVersion (4) cũng trả về true, thì phiên bản xấu đầu tiên là 4

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Khi n <2, thì trả về n
• Thực hiện phương pháp tìm kiếm nhị phân để phát hiện phiên bản không hợp lệ bằng cách sử dụng hàm đã cho.

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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