Leetcode 278 Solution

This article provides solution to leetcode question 278 (first-bad-version)

https://leetcode.com/problems/first-bad-version

Thinking Process

Very basic binary search problem. Using our binary search framework. isBadVersion is just our condition function. Put it in the binary_search_template, we get the final result.

Time & Space Complexity

Assuming N is the size of the array:

  • Time complexity: O(lg N)
  • Space complexity: O(1)

Solution

# The isBadVersion API is already defined for you. # def isBadVersion(version: int) -> bool:
class Solution: def firstBadVersion(self, n: int) -> int: l = 1 r = n
while l < r: m = (l + r) // 2
if isBadVersion(m): r = m else: l = m + 1 return l