เวอร์ชันแรกที่ไม่ดีใน Python

สมมติว่าในบริษัทหนึ่ง Product Manager เป็นผู้นำทีมที่พัฒนาผลิตภัณฑ์ใหม่ สมมติว่าเวอร์ชันล่าสุดไม่ผ่านการตรวจสอบคุณภาพ เนื่องจากแต่ละเวอร์ชันได้รับการพัฒนาตามเวอร์ชันก่อนหน้า เวอร์ชันทั้งหมดหลังจากเวอร์ชันที่เสียหายจะไม่ดี ดังนั้นเราจึงมีอาร์เรย์ A ที่มีองค์ประกอบ n [1, 2, … n] และเราต้องหาเวอร์ชันที่ไม่ดีตัวแรกจากอาร์เรย์นี้

พิจารณาว่าเรามีฟังก์ชัน isBadVersion(version_id) ซึ่งจะคืนค่าว่าเวอร์ชันนั้นเสียหรือไม่ ตัวอย่างเช่น สมมติว่า n =5 และเวอร์ชัน =4 เป็นเวอร์ชันแรกที่ไม่ดี ดังนั้นหาก isBadVersion(3) คืนค่าเท็จ isBadVersion(5) คืนค่าจริง และ isBadVersion(4) คืนค่าจริงด้วย ดังนั้นเวอร์ชันแรกที่ไม่ดีคือ 4

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• เมื่อ n <2 ให้คืนค่า 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)

อินพุต

5
4

ผลลัพธ์

4