Foros del Web » Programación para mayores de 30 ;) » C/C++ »

No comprendo esta parte (busqueda binaria)

Estas en el tema de No comprendo esta parte (busqueda binaria) en el foro de C/C++ en Foros del Web. Buenos dias!... soy nuevo en el foro y antes que nada... holaaa!!... jaja. Bueno, resulta que hace alrededor de una 1 semana, decidi comenzar un ...
  #1 (permalink)  
Antiguo 30/03/2011, 20:56
 
Fecha de Ingreso: marzo-2011
Mensajes: 5
Antigüedad: 13 años
Puntos: 0
No comprendo esta parte (busqueda binaria)

Buenos dias!... soy nuevo en el foro y antes que nada... holaaa!!... jaja. Bueno, resulta que hace alrededor de una 1 semana, decidi comenzar un curso de C de esos que andan por internet.. pero lo mas detallado posible. encontre uno bastante bueno (y bastante extenso)... y hasta el dia de hoy, el aprendizaje junto con la compilacion de mis primeros programas con turbo c++ 4.5... ivan de la mano. y de hecho todavia van de la mano, solo que me inquieta no saber a que se refiere una parte del codigo de la seccion de "busqueda binaria"... es decir, entiendo el codigo, pero no entiendo como es que las variables "bajo y alto" actuan en el siguiente codigo:

#include <stdio.h>
#include <conio.h>
#define BUC 50

main()
{
int vector[BUC], num, resultado, a, mitad,c;
for(a=0;a<=BUC-1;a++)
{
vector[a]=a*2;
}
printf("pone un num para buscar en el vector:\t");
scanf("%d",&num);
int bajo=0,alto= BUC-1;
while (bajo<=alto)
{
mitad = (bajo+alto)/2;
if(num==vector[mitad])
resultado=mitad;
if(num<vector[mitad])
alto= mitad -1;
else
bajo= mitad +1;
}
if(resultado!= -1)
printf("num %d encontrado en posicion %d",num,resultado);
else
printf("numero no encontrado");
getch;
return 0;
}

es decir, lo que no entiendo es como hace este programa, mediante estas variables... para llegar al resultado, y encontrar el numero buscado. si alguien puede darme una explicacion mas o menos detallada de lo que aqui sucede, lo agradeceria, ya que al leer el codigo, todavia no me cierra como es que se llega al resultado... lamento no poder ser mas explicito, pero es que no se como explicar bien lo que no entiendo. gracias de antemano, y espero entender esta parte por que si no debere abandonar el lenguaje ya que esto es practicamente lo mas basico del mismo. Muchas Gracias!.
  #2 (permalink)  
Antiguo 30/03/2011, 21:53
 
Fecha de Ingreso: junio-2005
Mensajes: 93
Antigüedad: 18 años, 10 meses
Puntos: 9
Respuesta: No comprendo esta parte (busqueda binaria)

ANTES QUE NADA TE RECOMENDARIA QUE ENTENDIERAS COMO FUNCIONA UNA BUSQUEDA BINARIA.

SABES LO QUE UN GRAFO?, UN ARBOL? , UN ARBOL BINARIO?

http://es.wikipedia.org/wiki/%C3%81rbol_binario

AQUI UNA PAGINA PARA QUE TE DES UNA IDEA
  #3 (permalink)  
Antiguo 31/03/2011, 02:18
Avatar de Heimish2000  
Fecha de Ingreso: enero-2011
Ubicación: Madrid
Mensajes: 844
Antigüedad: 13 años, 2 meses
Puntos: 89
Respuesta: No comprendo esta parte (busqueda binaria)

Después de lo que te ha dicho dragg04 yo te aconsejaría que lo programaras tú y fueras ejecutándolo paso a paso y mirando que se hace en cada paso.
  #4 (permalink)  
Antiguo 31/03/2011, 13:35
 
Fecha de Ingreso: marzo-2011
Mensajes: 5
Antigüedad: 13 años
Puntos: 0
Respuesta: No comprendo esta parte (busqueda binaria)

gracias dragg... voy a pegarle una leida... espero que este articulo no se valla mucho por las ramas... voy a ver si logro comprenderlo.
  #5 (permalink)  
Antiguo 31/03/2011, 13:49
 
Fecha de Ingreso: marzo-2011
Mensajes: 5
Antigüedad: 13 años
Puntos: 0
Pregunta Respuesta: No comprendo esta parte (busqueda binaria)

Cita:
Iniciado por dragg04 Ver Mensaje
ANTES QUE NADA TE RECOMENDARIA QUE ENTENDIERAS COMO FUNCIONA UNA BUSQUEDA BINARIA.

SABES LO QUE UN GRAFO?, UN ARBOL? , UN ARBOL BINARIO?

[url]http://es.wikipedia.org/wiki/%C3%81rbol_binario[/url]

AQUI UNA PAGINA PARA QUE TE DES UNA IDEA
Bueno... ya lei el articulo. la verdad... es muy circular... y toca muy poco del lenguaje... en sintesis es pura teoria y deberia aplicarse mas al lenguaje, para poder entenderlo... es decir que si bien, entendi el articulo, no veo como me ayuda con mi problema.
  #6 (permalink)  
Antiguo 31/03/2011, 16:05
 
Fecha de Ingreso: abril-2010
Ubicación: Rosario
Mensajes: 1.850
Antigüedad: 14 años
Puntos: 228
Respuesta: No comprendo esta parte (busqueda binaria)

Me parece que estan confundiendo de algoritmos. Una cosas es un arbol binaria y realizar una busqueda en ese arbol. Otra cosas es realizar una busqueda binaria en un secuencia de objetos ordenados.

Segun veo el algoritmo que tenes ahi se trata de la segunda opcion. Lo que se quiere hacer es encontrar un numero en un array. Lo que se va hacer es dividir el array en dos y fijarse en que zona quedo tu numero. Al estar ordenado esto es facil porqeu lo comparas si es mayor o menor. Una vez que tenes una zona del array volves a partir en dos y te quedas con la parte mas chica. Asi sucecivamente.

Ahora bien, se utilizan las variables bajo y alto para mantener los indices de las zonas. Es por eso que se busca una mitad (mitad = (baja+ alto )/ 2;) y luego se comparan los elemenos uqe estan en esos indices segun el segmentos que te tenes que quedar asginas mitad a bajo o alto y ahi corre de nuevo el ciclo....

Sobre tu respuesta anterior...primero que todo es fundamental entender el algoritmo, sin importar que lenguaje se usa.... ya que si lo entiendes directamente podrias programarlo tu y no tener que copiar otros algoritmos.
  #7 (permalink)  
Antiguo 31/03/2011, 16:32
 
Fecha de Ingreso: marzo-2011
Mensajes: 5
Antigüedad: 13 años
Puntos: 0
Respuesta: No comprendo esta parte (busqueda binaria)

Cita:
Iniciado por sam90 Ver Mensaje
Me parece que estan confundiendo de algoritmos. Una cosas es un arbol binaria y realizar una busqueda en ese arbol. Otra cosas es realizar una busqueda binaria en un secuencia de objetos ordenados.

Segun veo el algoritmo que tenes ahi se trata de la segunda opcion. Lo que se quiere hacer es encontrar un numero en un array. Lo que se va hacer es dividir el array en dos y fijarse en que zona quedo tu numero. Al estar ordenado esto es facil porqeu lo comparas si es mayor o menor. Una vez que tenes una zona del array volves a partir en dos y te quedas con la parte mas chica. Asi sucecivamente.

Ahora bien, se utilizan las variables bajo y alto para mantener los indices de las zonas. Es por eso que se busca una mitad (mitad = (baja+ alto )/ 2;) y luego se comparan los elemenos uqe estan en esos indices segun el segmentos que te tenes que quedar asginas mitad a bajo o alto y ahi corre de nuevo el ciclo....

Sobre tu respuesta anterior...primero que todo es fundamental entender el algoritmo, sin importar que lenguaje se usa.... ya que si lo entiendes directamente podrias programarlo tu y no tener que copiar otros algoritmos.

Excelente... esto es lo que no entendia... ahora si me quedo claro... muchas gracias por tu ayuda... si... entiendo el algoritmo, pero me queje de que en el articulo no se aplicaba al lenguaje. de nuevo gracias por la ayuda... que anes biennn.
  #8 (permalink)  
Antiguo 31/03/2011, 17:31
 
Fecha de Ingreso: junio-2005
Mensajes: 93
Antigüedad: 18 años, 10 meses
Puntos: 9
Respuesta: No comprendo esta parte (busqueda binaria)

kazekirino, un algoritmo no tiene que aplicar precisamente a un lenguaje en particular,
  #9 (permalink)  
Antiguo 01/04/2011, 16:10
 
Fecha de Ingreso: marzo-2011
Mensajes: 5
Antigüedad: 13 años
Puntos: 0
Respuesta: No comprendo esta parte (busqueda binaria)

Cita:
Iniciado por dragg04 Ver Mensaje
kazekirino, un algoritmo no tiene que aplicar precisamente a un lenguaje en particular,
ya lo se y gracias por la leccion... pero no me gusto que tu articulo no fuera mas explicito respecto a mi problema. me explico?.

Etiquetas: Ninguno
Atención: Estás leyendo un tema que no tiene actividad desde hace más de 6 MESES, te recomendamos abrir un Nuevo tema en lugar de responder al actual.
Respuesta




La zona horaria es GMT -6. Ahora son las 17:09.