สมมติว่าในบริษัทหนึ่ง มีผู้จัดการผลิตภัณฑ์นำทีมที่พัฒนาผลิตภัณฑ์ใหม่ สมมติว่าเวอร์ชันล่าสุดล้มเหลวในการตรวจสอบคุณภาพ เนื่องจากแต่ละเวอร์ชันพัฒนาจากเวอร์ชันก่อนหน้า ทุกเวอร์ชันหลังจากเวอร์ชันที่ผิดจะเป็นเวอร์ชันที่ผิดเช่นกัน ดังนั้นเราจึงมีอาร์เรย์ A ที่มี n องค์ประกอบ [1, 2, ... n] และเราต้องหาเวอร์ชันแรกที่ผิดจากอาร์เรย์นี้
พิจารณาว่าเรามีฟังก์ชัน isBadVersion(version_id) ฟังก์ชันนี้จะคืนค่าว่าเวอร์ชันนั้นผิดหรือไม่ ตัวอย่างเช่น สมมติ n = 5 และเวอร์ชัน = 4 เป็นเวอร์ชันแรกที่ผิด ถ้า isBadVersion(3) คืนค่า false isBadVersion(5) คืนค่า true และ isBadVersion(4) ก็คืนค่า true เวอร์ชันแรกที่ผิดคือ 4
วิธีการแก้ปัญหา
- เมื่อ n < 2 ให้คืนค่า n
- ทำการค้นหาแบบทวิภาค (binary search) เพื่อตรวจจับเวอร์ชันที่ผิดโดยใช้ฟังก์ชันที่กำหนด
ตัวอย่างโค้ด
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
