Algoritmos y Estructuras de Datos - VJ1215

Ejemplos de errores en el ejercicio 4 del tema 1

Esto son ejemplos de errores cometidos por estudiantes. Piensa qué es lo que está mal.

Ejemplo de solución incorrecta 1

int busquedaBinariaRecursiva(const vector<int> & v, int dato, int inicio, int fin) {
   if (inicio <= fin) {
      int medio = (inicio + fin) / 2;
      if (v[medio] < dato)
	 busquedaBinariaRecursiva(v, dato, medio + 1, fin);
      else if (v[medio] > dato)
	 busquedaBinariaRecursiva(v, dato, inicio, medio - 1);
      else
	 return medio;
   }
   return -1;
}

int busquedaBinariaRecursiva(const vector<int> & v, int dato) {
   busquedaBinariaRecursiva(v, dato, 0, v.size() - 1);
}

¿Por qué es incorrecta?

Falta siempre return para devolver el resultado de las llamadas recursivas.

Ejemplo de solución incorrecta 1.b

int busquedaBinariaRecursiva(const vector<int> & v, int dato, int inicio, int fin) {
   if (inicio <= fin) {
      int medio = (inicio + fin) / 2;
      if (v[medio] < dato)
	 return busquedaBinariaRecursiva(v, dato, medio + 1, fin);
      else if (v[medio] > dato)
	 return busquedaBinariaRecursiva(v, dato, inicio, medio - 1);
      else
	 return medio;
   }
   return -1;
}

int busquedaBinariaRecursiva(const vector<int> & v, int dato) {
   busquedaBinariaRecursiva(v, dato, 0, v.size() - 1);
}

¿Por qué es incorrecta?

Falta un return.

Ejemplo de solución incorrecta 2

int busquedaBinariaRecursiva(const vector<int> & v, int dato, int inicio, int fin) {
   int medio = (inicio + fin) / 2;
   if (v[medio] < dato)
      return busquedaBinariaRecursiva(v, dato, medio + 1, fin);
   else if (v[medio] > dato)
      return busquedaBinariaRecursiva(v, dato, inicio, medio - 1);
   else
      return medio;
   return -1;
}

int busquedaBinariaRecursiva(const vector<int> & v, int dato) {
   return busquedaBinariaRecursiva(v, dato, 0, v.size() - 1);
}

¿Por qué es incorrecta?

Esta solución es incorrecta, porque return -1 así es inalcanzable.

Ejemplo de solución incorrecta 3

int busquedaBinariaRecursiva(const vector<int> & v, int dato, int inicio, int fin) {
   if (inicio <= fin) {
      int medio = (inicio + fin) / 2;
      if (v[medio] < dato)
	 return busquedaBinariaRecursiva(v, dato, medio + 1, fin);
      else if (v[medio] > dato)
	 return busquedaBinariaRecursiva(v, dato, inicio, medio - 1);
      else
	 return medio;
   }
   return -1;
}

int busquedaBinariaRecursiva(const vector<int> & v, int dato) {
   return busquedaBinariaRecursiva(v, dato, 0, v.size());
}

¿Por qué es incorrecta?

Esta solución es incorrecta, porque donde debe poner v.size() - 1 pone v.size().

Ejemplo de solución incorrecta 4

int busquedaBinariaRecursiva(const vector<int> & v, int dato, int inicio, int fin) {
   if (inicio <= fin) {
      int medio = (inicio + fin) / 2;
      if (v[medio] < dato)
	 return busquedaBinariaRecursiva(v, dato, medio, fin);
      else if (v[medio] > dato)
	 return busquedaBinariaRecursiva(v, dato, inicio, medio);
      else
	 return medio;
   }
   return -1;
}

int busquedaBinariaRecursiva(const vector<int> & v, int dato) {
   return busquedaBinariaRecursiva(v, dato, 0, v.size() - 1);
}

¿Por qué es incorrecta?

Esta solución es incorrecta, porque donde debe poner medio + 1 o medio -1 pone medio.