Título: Modificar busqueda binaria Publicado por: mari2diaz en 12 Abril 2022, 23:51 pm modifique la búsqueda binaria de manera que la función devuelva el índice del primer elemento mayor al que se está buscando y -1 en caso de que no exista ningún elemento mayor
si elijo cualquier otro numero q no sea el 144 funciona el programa, no se q estoy haciendo mal o hay una mejor forma de hacerlo Código
Título: Re: Modificar busqueda binaria Publicado por: Serapis en 13 Abril 2022, 00:56 am Tu problema está en el bucle while dentro de la condición de coincidencia...
Pasando 144, se localiza en el penúltimo índice, le pides que localiza los que sean iguales para tratar de devolver el último de ellos con el mismo valor, hay uno más... pero en tu bucle sigues aumentando el índice sin comprobar si se alcanzó el final del array. Una mejor manera es hacer justo lo contrario (en cierto modo), devolver el índice donde debiera ubicarse si no existe, o el primer lugar donde exista. Dado que el índice 0, siempre existe, si resulta ser menor que todo el array o igual al primer elemento, devuelve 0, con lo cual siempre estará bien ubicado, y no incurres en error. Mejor aún es simplemente devolver ese índice, sin tratar de buscar los que le preceden o siguen de igual valor... ya si por ejemplo se tratara de insertar un elemento, que más da, que se inserte el primero, el 5 de 10 o el 10 (si antes eran 9). tu al final tras la inserción tendrías (por ejemplo): ...x, x, x, x 144, 144, 144, 144, 144, 144, 144, 144, 144, 144, y, y, y, y... Cuál de esos 144 es el que tu has añadido?. No suele importar si no tiene más datos asociados. Código: Hacer mientras (bajo <= alto) Si a pesar de todo deseas mantener tu código, lo comento en detalle... Observa el problema paso a paso... el array tiene 15 elementos que van del indice 0 al 14. Hay dos casos, que accedas primero al indice 13 o primero al indice 14... A - En el indice 13 localiza, el valor 144: luego entra en el bucle, ya que el índice 13 es menor que el size-1 del array. Ahora evalúa si el valor es menor que el recién enconttrado (en el índice 13), no es verdad luego incrementa centro y regresa a la condición del bucle... ahora se alcanzó el límite del bucle, lo que impide seguir ejecutándolo, sale del bucle y luego del externo y por tanto devuelve -1 B - En el indice 14 localiza el valor 144: El bucle while impide entrar al mismo, pues es el último en el array, sale del bucle interno y luego del externo y devuelve -1 Tú codigo funcionaría, si tras dichos valores hubiera un elemento más (mayor lógicamente que los previos). Pero entonces tendría el mismo problema con ése... es decir siempre con el último (o últimos, si son iguales). Tu código debe quedar así: Código Nota las dos líneas (4 y 10) que he añadido y la 5 modificado. Título: Re: Modificar busqueda binaria Publicado por: jca1 en 26 Mayo 2022, 19:30 pm Esta seria otra manera
Código: Hacer mientras (bajo < alto) //(cuando bajo=alto la busqueda llega al final) Este pseudocodigo esta generalizado para buscar el primer valor mayor a cualquier numero que utilices como dato de entrada. Es decir que no es necesario que ese numero este en el arreglo. Si tenes como premisa que el dato de entrada es un numero que se encuentra en el arreglo, que creo que es este el caso que planteaste, seria asi Código: hacer mientras (bajo <= alto) La primera solucion de Serapis devuelve el indice donde esta la clave y no el siguiente mayor. Título: Re: Modificar busqueda binaria Publicado por: dijsktra en 1 Junio 2022, 21:51 pm Te paso la original y una variación que devuelve el indice del primer número mayor y en caso contrario devuelve el tamaño del vector size . (Esto es más natural que -1..)
Tu ya lo cambias si quieres. Código
EDIT: La linea Código: while (V[h]!= elem || (h<N-1 && V[h]==V[h+1])) // <= B: Changes. La salida da Código: Buscar numero: 8 Código: Buscar numero: 144 No quiero abrumar con formalismos. Fijate especialmente en:
Un saludo. Título: Re: Modificar busqueda binaria Publicado por: jca1 en 2 Junio 2022, 04:22 am while (V[h]!= elem || (elem!=N-1 && V[h]==V[h+1])) // <= B: Changes. La solucion que planteaste seria la correcta ya que cumple el sentido de busqueda binaria exactamente. Solo en la comparacion para verificar si estas en la ultima posicion, es "h" en vez de "elem". Si no hay valores mayores, "h" termina siendo igual a "N-1" cuando termina el ciclo y despues devuelve "h+1", que es igual al tamaño del arrreglo. Saludos. Título: Re: Modificar busqueda binaria Publicado por: dijsktra en 2 Junio 2022, 05:37 am ;-) ;-) ;-) ;-) Gracias jca1!
1000 veces lo hubiera visto y 1000 veces no me habría dado cuenta del error tipográfico. Corrijo en el original , poniendo EDIT y dando crédito. Título: Re: Modificar busqueda binaria Publicado por: dijsktra en 2 Junio 2022, 06:12 am Si tenes como premisa que el dato de entrada es un numero que se encuentra en el arreglo, que creo que es este el caso que planteaste, seria asi Código: hacer mientras (bajo <= alto) La primera solucion de Serapis devuelve el indice donde esta la clave y no el siguiente mayor. Ésta, -si fuese correcta, que depende de los valores iniciales de alto y bajo- no es efficiente como la búsqueda binaria, sino que degrada a busqueda lineal O(n)... Imagina un millon de 1´s y la ultima posición es 2... Código: 11111.....112 La que yo expuse, iteraría como mucho 20 (<= log_2 10^6) Título: Re: Modificar busqueda binaria Publicado por: jca1 en 2 Junio 2022, 21:27 pm Ésta, -si fuese correcta, que depende de los valores iniciales de alto y bajo- no es efficiente como la búsqueda binaria, sino que degrada a busqueda lineal O(n)... Si tienes razon! Me olvide de acotar que esa solucion no es eficiente por eso. No pude modificarla asi que muy bien aclarado, igual no es necesario ya. Gracias dijsktra! Este es el algoritmo referido: Código: hacer mientras (bajo <= alto) Saludos! |