LeetCode – Primera versión incorrecta (Java)

Usted es gerente de producto y actualmente lidera un equipo para desarrollar un nuevo producto. Desafortunadamente, la última versión de su producto no pasa el control de calidad. Dado que cada versión se desarrolla en base a la versión anterior, todas las versiones posteriores a una versión incorrecta también son malas.

Suponga que tiene n versiones [1, 2, …, n] y quieres descubrir el primero malo, lo que hace que todos los siguientes sean malos.

Se le proporciona una API bool isBadVersion (versión) que devolverá si la versión es incorrecta. Implemente una función para encontrar la primera versión incorrecta. Debe minimizar la cantidad de llamadas a la API.

Solución Java 1 – Recurisve

public int firstBadVersion(int n) {
    return helper(1, n);
}
 
public int helper(int i, int j){
    int m = i + (j-i)/2;
 
    if(i>=j)
        return i;
 
    if(isBadVersion(m)){
        return helper(i, m);
    }else{
        return helper(m+1, j); //not bad, left --> m+1
    }
}

Solución Java 2: iterativa

public int firstBadVersion(int n) {
    int i = 1, j = n;
    while (i < j) {
        int m = i + (j-i) / 2;
        if (isBadVersion(m)) {
            j = m;
        } else {
            i = m+1;
        }
    }
 
    if (isBadVersion(i)) {
        return i;
    }
 
    return j;
}