Bad Commit

There is a bug in your code. You’re not certain which commit number introduced the bug into the repo, but you know for certain an earlier commit number where it didn’t exist yet. A magical function, isBad(), determines if the commit is bad or not.

func isBad(commit: Int) -> Bool

Given isBad, determine which commit introduced the bug.

For n commits, this can be solved with a binary search in O(log n). Careful not to make an off-by-one mistake and return the bad commit rather than the commit preceding it.

func badCommit(pastCommit: Int, currentCommit: Int) -> Int {
  var left = pastCommit
  var right = currentCommit
  var mid = (left + right) / 2
  
  while (left < right) {
    if !isBad(commit: mid) {
      left = mid + 1
    }
    else {
      right = mid
    }
    
    mid = (left + right) / 2
  }
  
  return right
}

badCommit(pastCommit: 110, currentCommit: 334)