iOS Interview - Leetcode 278. First Bad Version

May 16, 2024 • 2 min read • #swift, #interview, #leetcode

Primary idea: Binary search, adjust left and right pointers to narrow down the search space by checking if the middle is bad version.
Time Complexity: O(logn)
Space Complexity: O(1)

var badVersion: Int = 0

func isBadVersion(_ i: Int) -> Bool {
    if i == badVersion {
        print("call isBadVersion(\(i)) -> true")
        return true
    } else {
        print("call isBadVersion(\(i)) -> false")
        return false
    }
}

func firstBadVersion(_ n: Int) -> Int {
    // Initialise the search space
    var left = 1
    var right = n
    var middle = 0

    while left < right {
        // Find the middle of the current search space
        middle = left + (right - left) / 2

        // Adjust left and right pointers depending on whether the middle is bad or good version
        if !isBadVersion(middle) {
            left = middle + 1
        } else {
            right = middle
        }
    }

    return left
}


badVersion = 4
print(firstBadVersion(5)) // 4
//call isBadVersion(3) -> false
//call isBadVersion(4) -> true

badVersion = 1
print(firstBadVersion(1)) // 1

badVersion = 2
print(firstBadVersion(2)) // 2
//call isBadVersion(1) -> false