elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Tutorial básico de Quickjs


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  [C] Búsqueda binaria recursiva
0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: [C] Búsqueda binaria recursiva  (Leído 19,153 veces)
BatchianoISpyxolo

Desconectado Desconectado

Mensajes: 166


Ver Perfil
[C] Búsqueda binaria recursiva
« en: 29 Octubre 2012, 18:54 pm »

Este pequeñito aporte va dedicado especialmente a aquellos que comienzan recién en la programación :D

Prerrequisitos (?)

→ Vectores
→ Saber qué es y cómo se lleva a cabo la búsqueda binaria

Adjunto el código del algoritmo no recursivo (Por: Rodrigo Burgos Domínguez.):
http://algorithmmx.blogspot.com.es/2011/11/algoritmo-de-busqueda-binaria.html

Código
  1. int busqueda_binaria(vector <int> list, int val){
  2.   int der = list.size() - 1, izq = 0, m;
  3.   while(izq <= der){
  4.      m = (izq + der) / 2;
  5.      if(m == list[val]) return m; //la posicion del valor
  6.      if(m > list[val]) der = m – 1;
  7.      else izq = m + 1;
  8.   }
  9.   return -1; // no se encontro el dato :P
  10. }

Teniendo en cuenta que ya sabemos la lógica que sigue este algoritmo y su implementación arriba expuesta, vamos a pensar en hacerlo de forma recursiva, es decir, que la misma función vaya reduciendo el tamaño (N) del problema a un caso base, de tal manera, al conocer la solución del caso base, va a poder dar solución a cualquier problema de tamaño N.

Entonces el código sería el siguiente:

(utilizo int casting para no usar la librería math.h)

Código
  1. int BinarySearch(int x, int v[], int tam) {
  2.  
  3.    int RecursiveBinarySearch(int x, int v[], int i, int m, int d) {
  4.        if (i>d) return -1;
  5.        else if ( x == v[m] ) return m;
  6.        else if ( x < v[m] ) return RecursiveBinarySearch(x, v, i, (int)((i+m-1)/2), (m-1));
  7.        else return RecursiveBinarySearch(x, v, (m+1), (int)((d+m+1)/2), d);
  8.    }
  9.  
  10.    int i = 0;
  11.    int m = tam/2;
  12.    int d = tam;
  13.  
  14.    return RecursiveBinarySearch(x, v, i, m, d);
  15.  
  16. }

Explicación general:

La premisa que tenemos es que nosotros tenemos que buscar un elemento x en un vector v de tamaño N que está previamente ordenado. Teniendo eso en cuenta podemos afirmar que cualquier subvector w de v de tamaño [0..N] también está ordenado.

Pues teniendo eso en cuenta vamos reduciendo el tamaño del problema (N) a la mitad en cada llamada recursiva. ¿Por qué? Porque si x no es el elemento medio del vector v de tamaño N, entonces verificamos si es menor o mayor que él. Si es menor, buscamos en el subvector de tamaño N/2 izquierdo, sino en el derecho.

Como véis, en este caso, el algoritmo se pasa de forma cíclica a forma recursiva casi sin pensar. ¿Por qué? Estamos ante una Tail Recursive Function (la autollamada es lo último que se hace) y podemos pensar en definitiva que estamos ejecutando un ciclo simplemente.

Podría aquí estar escribiendo horas y horas sobre algoritmos de búsqueda y ordenación pero no es plan xD

Decir simplemente que hay tener en cuenta que el vector en el que vayamos a buscar un elemento, debe estar previamente ordenado.

En este momento os preguntaréis: ¿Qué me conviene más, buscar directamente en un vector con la búsqueda lineal o es mejor ordenarlo previamente (quicksort) y luego aplicar búsqueda binaria? Bueno eso ya son temas de complejidad algorítmica y haciendo un pequeño estudio se puede sacar conclusiones.

Decir también que hay estructuras de datos eficientes para la búsqueda como lo son por ejemplo las Tablas Hash o los Árboles Binarios de Búsqueda, ABB (variante AVL), por ejemplo.

Bueno con esto y un bizcocho me despido.

¡Saludos!

Todos los comentarios serán bien recibidos :)


« Última modificación: 29 Octubre 2012, 23:13 pm por BatchianoISpyxolo » En línea

Puede que desees aprender a programar desde 0: www.espascal.es
Stakewinner00


Desconectado Desconectado

Mensajes: 1.426



Ver Perfil WWW
Re: [C] Búsqueda binaria recursiva
« Respuesta #1 en: 29 Octubre 2012, 22:59 pm »

Hoy pase a releer las normas y me vi que casi nadie las cumplia al 100%.

Felicidades eres de los pocos que cumplen las normas creo  ;-).


En línea

BatchianoISpyxolo

Desconectado Desconectado

Mensajes: 166


Ver Perfil
Re: [C] Búsqueda binaria recursiva
« Respuesta #2 en: 29 Octubre 2012, 23:06 pm »

Hoy pase a releer las normas y me vi que casi nadie las cumplia al 100%.

Felicidades eres de los pocos que cumplen las normas creo  ;-).

Será eso de la experiencia... jaja
En línea

Puede que desees aprender a programar desde 0: www.espascal.es
flony


Desconectado Desconectado

Mensajes: 583



Ver Perfil
Re: [C] Búsqueda binaria recursiva
« Respuesta #3 en: 29 Octubre 2012, 23:08 pm »

para leer  ;-)
En línea

si un problema no tiene solucion entonces no es un problema...es algo inevitable
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
busqueda binaria
Programación C/C++
Sunshine66 3 4,358 Último mensaje 6 Mayo 2010, 07:42 am
por Akai
Busqueda binaria con palabras
Programación C/C++
soez 0 2,953 Último mensaje 3 Agosto 2010, 04:10 am
por soez
Busqueda binaria.
Java
NetJava 6 8,938 Último mensaje 28 Marzo 2011, 18:20 pm
por NetJava
Busqueda recursiva
Programación C/C++
s3tH 7 8,462 Último mensaje 6 Mayo 2012, 02:46 am
por david_BS
Me pueden ayudar a hacer una Búsqueda Binaria Recursiva Dinamica
Programación C/C++
gibranini 4 3,695 Último mensaje 8 Julio 2014, 19:20 pm
por gibranini
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines