First Bad Version

Условие

Вы разработали некий API, который сообщает, является ли версия хорошей или плохой. Определите номер первой плохой версии, которая является последующей версией всех хороших.

Примеры

Input: n = 5, bad = 4

Output: 4

Explanation:

Вызов isBadVersion(3) → false.
Вызов isBadVersion(5) → true.
Вызов isBadVersion(4) → true.
Поэтому 4 - первая плохая версия.

Input: n = 1, bad = 1

Output: 1

Решение

/* The isBadVersion API is defined in the parent class VersionControl.
      fun isBadVersion(version: Int) : Boolean {} */
class Solution: VersionControl() {
    
    override fun firstBadVersion(n: Int) : Int {
        var left = 1 // Начало диапазона
		    var right = n // Конец диапазона

		    while (left < right) {
		        val mid = left + (right - left) / 2 // Находим середину
		        if (isBadVersion(mid)) {
		            right = mid // Если версия плохая, ищем в левой половине
		        } else {
		            left = mid + 1 // Если версия хорошая, ищем в правой половине
		        }
		    }

		    return left // Возвращаем первую плохую версию
	  }
}

Временная сложность

O(log n), так как мы используем двоичный поиск для нахождения первой плохой версии.

Пространственная сложность

O(1), так как мы используем фиксированное количество переменных.