Задача с собеседования: Первая плохая версия

Может использоваться на собеседовании в FAANG как разогревочная.

Задача. Есть некий программный продукт. У него есть версии от 1, 2, ...n.
Известно, что начиная с некой версии все последующие версии плохие. Например, если у нас версии 1, 2, 3, 4, ...10, и начиная с версии 6 все версии плохие. Т.е. версии 6, 7, 8, 9, 10 - плохие. Также у нас есть функция boolean isBadVersion(int version), которая возвращает версия плохая или нет.
Нужно написать функцию, которая вернет первую плохую версию. Нужно минимизировать число вызовов функции isBadVersion.

Решение. Первое решение, которое приходит в голову - линейный поиск. Пройтись циклом по всем версиям , начиная с первой, и вызвать функцию isBadVersion. Как только она вернет true - мы нашли нашу первую плохую версию. Такое решение работает за O(n).
Код решения:
public int firstBadVersion(int n) {
for (int version = 1; version <= n; version++) {
if (isBadVersion(version)) {
return version;
}
}
return -1;
}
Можно ли улучшить это решение? - Да. Можно применить бинарный поиск.
Вначале инициализируем левый указатель 1, а правый n. Найдем среднюю версию. Проверим, является ли она плохой. Если она плохая, то первая плохая версия или эта версия или она слева. Если она хорошая, то первая плохая точно справа. Если версия плохая, то надо или правый указатель двигать влево или мы нашли нашу первую плохую версию. Как отличить эти два случая? Можно проверить еще одну версию слева на единицу меньше. Если она хорошая, то мы нашли нашу первую плохую версию. Если она тоже плохая, то решение слева и нужно двигать правый указатель влево. Также тут может быть еще один edge-case - все версии плохие. Поэтому прежде чем проверять еще одну версию слева, проверим, что наша текущая версия это первая версия. Если она первая и плохая - то мы нашли ответ. Если мы не нашли еще первую плохую версию, то двигаем левый и правый указатель, сокращая тем самым область поиска в два раза. И проделываем тоже самое еще раз. Решение будет работать быстрее предыдущего - за O(log(n)).
Код решения:
public int firstBadVersion(int n) {
int left = 1;
int right = n;
while (left <= right) {
int mid = left + (right - left) / 2;
boolean isBad = isBadVersion(mid);
if (isBad && (mid == 1 || !isBadVersion(mid - 1))) {
return mid;
}
if (isBad) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}