/* The isBadVersion API is defined in the parent class VersionControl.
def isBadVersion(version: Int): Boolean = {} */

class Solution: VersionControl() {
override fun firstBadVersion(n: Int) : Int {

if(isBadVersion(n/2)){
for (i in n/2 downTo 0){
if(!isBadVersion(i)){
return i+1
}
}
}else {
for (i in n/2 .. n-1){
if(isBadVersion(i)){
return i
}
}
}

return n
}
}