Búsqueda Binaria Recursiva

Problema:

Dado un arreglo de números reales ordenado y un número real, escriba una función que retorne -1 si el número buscado no se encuentra en el arreglo o, en caso contrario, la posición del arreglo en la que se encuentra.

Ejemplos:

Entrada: tam=5, arr[]={1,2,3,4,5}, n=2 Salida: El elemento buscado se encuentra en la posicion 1. Entrada: tam=5, arr[]={1,2,3,4,5}, n=0 Salida: El elemento buscado no se encuentra en el arreglo.

Idea del algoritmo:

1. Se evalúa si la posición más a la izquierda (izq) es mayor a la de más a la derecha (der), si:

   -Es verdadero, la función retorna -1, en otras palabras, el número buscado no se encuentra en el arreglo.

   -Es falso: se realizan los siguientes pasos.

2. Se evalúa si el elemento medio del arreglo (arr[med]) es igual al número buscado (n).

3. Se evalúa si el elemento buscado es mayor al elemento del medio del arreglo. Si:

   -Es verdadero: se ejecuta nuevamente la función pasando como parámetro de elemento más a la izquierda a med+1.

   -Es falso: se ejecuta nuevamente la función pasando como parámetro de elemento más a la derecha a med-1.

Código:

Disponible en ejemplo Búsqueda Binaria Recursiva.

Ejemplo de uso:

Disponible en Búsqueda Binaria Recursiva.

Explicación animada:

Disponible en Binary vs Linear Search.

Complejidad:

La complejidad es del orden O(log n).

Problemas en sitios jueces: