Home Algoritmos y Estructuras de Datos (VJ1215)

Curso 2022/2023

Ejemplos de errores en el ejercicio 11 del tema 1

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

Error 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);
}

Solución

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

Error 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);
}

Solución

Falta un return.

Error 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);
}

Solución

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

Error 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());
}

Solución

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

Error 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);
}

Solución

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