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

 

 


Tema destacado: Trabajando con las ramas de git (tercera parte)


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

Desconectado Desconectado

Mensajes: 19


Ver Perfil
Modificar busqueda binaria
« 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
  1. #include <iostream>
  2.  
  3. int busquedaBinaria(int clave, int array[], int size);
  4.  
  5. int main(){
  6.  
  7. int numero;
  8. int size = 15;
  9. int array[size] = {0, 1, 1, 2, 3, 5, 8, 13, 13, 21, 34, 55, 89, 144, 144};
  10.  
  11. std::cout << "Buscar numero: ";
  12. std::cin >> numero;
  13.  
  14. if(busquedaBinaria(numero, array, size) > 0)
  15.    std::cout << "Array[" << busquedaBinaria(numero, array, size) << "] = " << array[busquedaBinaria(numero, array, size)] << std::endl;
  16. else
  17.    std::cout << "No hay elemento mayor a " << numero << std::endl;  
  18.  
  19. return 0;
  20. }
  21.  
  22. int busquedaBinaria(int clave, int array[], int size){
  23. int centro;
  24. int bajo = 0;
  25. int alto = size - 1;
  26. while(bajo <= alto){
  27. centro = (bajo + alto) / 2;
  28. if(clave == array[centro]){
  29. while(centro < (size - 1)){
  30. if(clave < array[centro])
  31.    return centro;
  32. centro++;
  33. }  
  34. }else if(clave < array[centro])
  35.    alto = centro - 1;
  36. else
  37.    bajo = centro + 1;    
  38. }
  39. return -1;
  40. }


En línea

Serapis
Colaborador
***
Desconectado Desconectado

Mensajes: 3.259


Ver Perfil
Re: Modificar busqueda binaria
« Respuesta #1 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)
    centro = (bajo + alto) / 2
    si (clave < array[centro])
        alto = centro - 1
    osi (clave < array[centro])
        bajo = centro + 1      
    sino          // (clave = array[centro])
devolver centro
    fin si
Repetir
devolver -1

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
  1. while(bajo <= alto){
  2.    centro = (bajo + alto) / 2;
  3.    if(clave == array[centro]){
  4.        centro++;
  5. while(centro <= (size - 1)){
  6.    if(clave < array[centro])
  7.        return centro;
  8.    centro++;
  9. }  
  10.        return centro;
  11.    }else if(clave < array[centro])
  12. alto = centro - 1;
  13.    else
  14. bajo = centro + 1;    
  15. }
  16. return -1;
  17.  
Nota las dos líneas (4 y 10) que he añadido y la 5 modificado.


« Última modificación: 13 Abril 2022, 01:00 am por Serapis » En línea

jca1

Desconectado Desconectado

Mensajes: 51


Ver Perfil
Re: Modificar busqueda binaria
« Respuesta #2 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)
    centro = (bajo + alto) / 2
    si(clave < array[centro])
        alto = centro //(no es -1 ya que se incluye a centro porque puede ser la soulcion tambien)
    sino
        bajo = centro + 1    
    fin si
si (clave<array[bajo]) //(al ser bajo=alto se puede usar cualquiera y es verdadero cuando existe solucion)
    devolver bajo
sino
    devolver -1; //(este caso solo sucede cuando bajo=size-1 y clave>=array[bajo], o sea cuando no existe solucion)

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)
    centro = (bajo + alto) / 2
    si (clave = array[centro])
        hacer mientras (centro < size)
            si (clave < array[centro])
                devolver centro
            centro = centro + 1
        Repetir
        devolver -1
    o si (clave < array[centro])
        alto = centro
    sino
        bajo = centro + 1
repetir

La primera solucion de Serapis devuelve el indice donde esta la clave y no el siguiente mayor.
« Última modificación: 29 Mayo 2022, 13:19 pm por jca1 » En línea

dijsktra

Desconectado Desconectado

Mensajes: 108


Mr Edsger Dijsktra (Tribute to)


Ver Perfil
Re: Modificar busqueda binaria
« Respuesta #3 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
  1. #include <iostream>
  2.  
  3. int binary_search(const int V[], const int N, const int elem);
  4. int binary_search2(const int V[], const int N, const int elem);
  5.  
  6. #define size 15
  7.  
  8. int main(){
  9.  
  10. int numero;
  11. int array[size] = {0, 1, 1, 2, 3, 5, 8, 13, 13, 21, 34, 55, 89, 144, 144};
  12.  
  13. std::cout << "Buscar numero: ";
  14. std::cin >> numero;
  15.  
  16. const int index = binary_search2(array, size,numero);
  17. if (index == size)
  18. std::cout << "No hay elemento mayor a " << numero << std::endl;
  19. else
  20. std::cout << "Array[" << index << "] = " << array[index] << std::endl;
  21.  
  22. return 0;
  23. }
  24.  
  25.  
  26. #define h ((i+j)/2)
  27.  
  28. /* P: N >= 1, V sorted , elem in V*/
  29. /* original */
  30. int binary_search(const int V[], const int N, const int elem)
  31. {
  32.    int i,j;
  33.    i=0;
  34.    j=N;
  35.    while (V[h]!= elem)
  36.        if (V[h]>elem) j=h;
  37.        else i=h+1;
  38.    return h;
  39. }
  40.  
  41. /* P: N >= 1, V sorted , elem in V*/
  42. /* Variation */
  43. int binary_search2(const int V[], const int N, const int elem)
  44. {
  45.    int i,j;
  46.    i=0;
  47.    j=N;
  48. // I : 0<= i < j <= N and V[i] <= V[elem] <= V[j-1]
  49.    while (V[h]!= elem || (h<N-1 && V[h]==V[h+1]))  // <= B: Changes.
  50.        if (V[h]>elem) j=h;
  51.        else i=h+1;
  52.    return h+1; // V[h] points to element.
  53. }
  54.  

EDIT: La linea
Código:
   while (V[h]!= elem || (h<N-1 && V[h]==V[h+1]))  // <= B: Changes.
tenía un error tipográfico. (Crédito: jca1)

La salida da

Código:
Buscar numero: 8
Array[7] = 13

Código:
Buscar numero: 144
No hay elemento mayor a 144

No quiero abrumar con formalismos. Fijate especialmente en:
  • la precondicion P: el array ordenado y el numero que pases tiene que existir
  • la parada B: A la derecha de h hay uno mayor,  o esta en ultima posicion

Un saludo.
« Última modificación: 2 Junio 2022, 05:45 am por dijsktra » En línea

Si la depuración es el proceso de eliminar fallos en el software, entonces programar debe ser el proceso de ponerlos dentro. (Edsger Dijsktra)
jca1

Desconectado Desconectado

Mensajes: 51


Ver Perfil
Re: Modificar busqueda binaria
« Respuesta #4 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.


« Última modificación: 2 Junio 2022, 04:47 am por jca1 » En línea

dijsktra

Desconectado Desconectado

Mensajes: 108


Mr Edsger Dijsktra (Tribute to)


Ver Perfil
Re: Modificar busqueda binaria
« Respuesta #5 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.
En línea

Si la depuración es el proceso de eliminar fallos en el software, entonces programar debe ser el proceso de ponerlos dentro. (Edsger Dijsktra)
dijsktra

Desconectado Desconectado

Mensajes: 108


Mr Edsger Dijsktra (Tribute to)


Ver Perfil
Re: Modificar busqueda binaria
« Respuesta #6 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)
    centro = (bajo + alto) / 2
    si (clave = array[centro])
        hacer mientras (centro < size)
            si (clave < array[centro])
                devolver centro
            centro = centro + 1
        Repetir
        devolver -1
    o si (clave < array[centro])
        alto = centro
    sino
        bajo = centro + 1
repetir

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
Entonces, el programa itera 500.000 veces, o sea O(N/2) = O(N).
La que yo expuse, iteraría como mucho 20 (<= log_2 10^6)
« Última modificación: 2 Junio 2022, 06:22 am por dijsktra » En línea

Si la depuración es el proceso de eliminar fallos en el software, entonces programar debe ser el proceso de ponerlos dentro. (Edsger Dijsktra)
jca1

Desconectado Desconectado

Mensajes: 51


Ver Perfil
Re: Modificar busqueda binaria
« Respuesta #7 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)
    centro = (bajo + alto) / 2
    si (clave = array[centro])
        hacer mientras (centro < size)
            si (clave < array[centro])
                devolver centro
            centro = centro + 1
        Repetir
        devolver -1
    o si (clave < array[centro])
        alto = centro
    sino
        bajo = centro + 1
repetir

Saludos!

« Última modificación: 2 Junio 2022, 21:46 pm por jca1 » En línea

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 3,739 Último mensaje 6 Mayo 2010, 07:42 am
por Akai
Busqueda binaria con palabras
Programación C/C++
soez 0 2,486 Último mensaje 3 Agosto 2010, 04:10 am
por soez
Busqueda binaria.
Java
NetJava 6 8,142 Último mensaje 28 Marzo 2011, 18:20 pm
por NetJava
[C] Búsqueda binaria recursiva
Programación C/C++
BatchianoISpyxolo 3 18,202 Último mensaje 29 Octubre 2012, 23:08 pm
por flony
busqueda binaria en archivo
Programación C/C++
m@o_614 5 4,824 Último mensaje 2 Enero 2014, 00:34 am
por m@o_614
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines