278. First Bad Version

Problem Statement

link: LeetCode.cn LeetCode

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which returns whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Example:

Input: n = 5, bad = 4 Output: 4

Input: n = 1, bad = 1 Output: 1

Solution Approach

The solution employs binary search to efficiently locate the first bad version in a given range of versions, minimizing the number of API calls by iteratively narrowing down the search interval based on whether the mid-version is identified as bad or not.

Algorithm

1. Binary Search Initialization: Initialize left (l) and right (r) pointers for the version range.

2. Iterative Binary Search: While l is less than r, check the mid-version for being bad. Update l or r accordingly to narrow down the search space.

3. Return Result: Once l surpasses r, return the value of l as the first bad version.

Implement

    class Solution:
  def firstBadVersion(self, n: int) -> int:
      l, r = 1, n
      while l < r:
          mid = (l + r) // 2
          isBad = isBadVersion(mid)
          if isBad:
              r = mid
          else:
              l = mid + 1
      return
     

    
    

Twitter  facebook  Email