力扣刷题（第六十四天）

灵感来源 

- 保持更新，努力学习

- python脚本学习

第一个错误的版本

解题思路

1. 初始化左右边界：左边界 left = 1，右边界 right = n。
2. 二分查找循环：
   • 计算中间版本号 mid。
   • 若 mid 是错误版本，说明第一个错误版本在 [left, mid] 中，更新右边界。
   • 若 mid 不是错误版本，说明第一个错误版本在 [mid+1, right] 中，更新左边界。
3. 终止条件：当 left 和 right 相遇时，即为第一个错误版本。

   # The isBadVersion API is already defined for you.
   # @param version, an integer
   # @return a bool
   # def isBadVersion(version):
   
   class Solution:
       def firstBadVersion(self, n):
           """
           :type n: int
           :rtype: int
           """
           left, right = 1, n
           
           while left < right:
               mid = left + (right - left) // 2  # 防止整数溢出
               
               if isBadVersion(mid):
                   # 第一个错误版本在[left, mid]中
                   right = mid
               else:
                   # 第一个错误版本在[mid+1, right]中
                   left = mid + 1
           
           # 循环结束时，left和right指向同一个位置
           return left

逐行解释

# The isBadVersion API is already defined for you.
# @param version, an integer
# @return a bool
# def isBadVersion(version):

class Solution:
    def firstBadVersion(self, n):
        """
        :type n: int
        :rtype: int
        """
        # 初始化左边界为第一个版本
        left = 1
        # 初始化右边界为最后一个版本
        right = n
        
        # 循环条件：左边界严格小于右边界
        # 当left == right时，循环结束，此时的left即为第一个错误版本
        while left < right:
            # 计算中间版本号，使用(left + right) // 2可能导致整数溢出
            # 例如当left和right都接近INT_MAX时，加法会溢出
            mid = left + (right - left) // 2
            
            # 检查中间版本是否为错误版本
            if isBadVersion(mid):
                # 如果中间版本是错误的，第一个错误版本可能是mid或在mid左侧
                # 因此更新右边界为mid（注意：没有减1，因为mid可能就是答案）
                right = mid
            else:
                # 如果中间版本不是错误的，第一个错误版本必然在mid右侧
                # 因此更新左边界为mid + 1
                left = mid + 1
        
        # 循环结束时，left和right指向同一个位置，即第一个错误版本
        return left