Miércoles 28 de Julio
Objetivos:
Temas:
Búsqueda binaria recursiva
Existe una variante de la búsqueda en un arreglo ordenado que puede
ser implementado naturalmente usando recursividad. La función
buscarBinRec busca un string x en un arreglo de string a,
en un intervalo de índices [imin,imax]. Esta función también retorna
el índice en donde se encuentra x. El algoritmo recursivo es:
- Caso base:
- Si imin>imax, el intervalo es vacío, por lo que x no se encuentra en
el arreglo en ese intervalo y se retorn -1.
- Si no, se calcula icentro=(imin+imax)/2 y se compara x con a[icentro].
Si son iguales, x se encuentra en a[icentro] por lo que se retorna icentro.
- Caso recursivo:
- Si x<a[icentro] se busca recursivamente en el intervalo [imin,icentro-1].
- Si x>a[icentro] se busca recursivamente en el intervalo [icentro+1,imax].
La función queda:
int buscarBinRec(String x, String[] a, int imin, int imax) {
if (imin>imax)
return -1;
int icentro= (imin+imax)/2;
int comp= compare(x, a[icentro]);
if (comp==0)
return icentro;
if (comp<0)
return buscarBinRec(x, a, imin, icentro-1);
else
return buscarBinRec(x, a, icentro+1, imax);
}