1

Espero me puedan ayudar, tengo un problema estoy realizando un programa de búsqueda binaria en un arreglo donde el usuario define el tamaño y el llenado del arreglo además del número que desea buscar el problema es que si por ejemplo ingresa los siguientes números: 1,2,3 y el quiere buscar el 4, yo necesito que le arroje que el número no se encuentra en el arreglo pero no sé como hacerlo. Les dejo lo que llevo del código:

public class BusquedaBinaria {

    int busquedaBinaria(int A[], int x, int i, int j) {

        int medio;
        if (i > j) {
            return 0;
        }
        medio = (i + j) / 2;
        if (A[medio] < x) {
            return busquedaBinaria(A, x, medio + 1, j);
        } else if (A[medio] > x) {
            return busquedaBinaria(A, x, i, medio - 1);
        } else {
            return medio + 1;
        }
    }
}

public class PruebaBusquedaBinaria {

    public static void main(String[] args) {
        BusquedaBinaria f = new BusquedaBinaria();
        Scanner scan = new Scanner(System.in);
        int n;
        System.out.println("Ingrese el tamaño del arreglo:");
        n=scan.nextInt();
        int A[]= new int[n];
        int s;
        System.out.println("Ingrese los numero para llenar el arreglo:");
        for (int i = 0; i <n; i++) {
            A[i]=scan.nextInt();
        }
        System.out.println("EL arreglo sin ordenar es:");
        for (int i = 0; i < n; i++) {
            System.out.print(A[i]+" ");   
        }
        System.out.println("");
        System.out.println("Los datos ordenados son: ");
        Arrays.sort(A);
        for (int i = 0; i <n; i++) {
            System.out.print(A[i]+" "); 
        }
        System.out.println(" ");
        System.out.println("ingrese el numero que desea buscar");
        int x = scan.nextInt();
      if(f.busquedaBinaria(A, x, 0, n)>=n){
          System.out.println("El numero no se encontro");
      }else{
          System.out.println("La posicion del numero fue: ");
          System.out.println(f.busquedaBinaria(A, x, 0, n));
      }
    }   
}

lo que yo estaba intentando era hacer el siguiente if(f.busquedaBinaria(A, x, 0, n)>=n) pero no me funciono.

6
  • En que momento, busqueda binaria devuelve el valor si lo encontro? eso es lo que falla.
    – gbianchi
    Commented el 25 sept. 2019 a las 1:01
  • entonces tendria que poner un return -1? o que me recomiendas hacer Commented el 25 sept. 2019 a las 1:03
  • usa nombres de variables que sirvan para algo (x, j, i no significan nada). en que momento, en tu codigo, te estas fijando si el valor que buscas es el mismo donde estas parado en la lista?
    – gbianchi
    Commented el 25 sept. 2019 a las 1:04
  • pues esta parte se encarga de hacer el analisis Commented el 25 sept. 2019 a las 1:09
  • int medio; if (i > j) { return 0; } medio = (i + j) / 2; if (A[medio] < x) { return busquedaBinaria(A, x, medio + 1, j); } else if (A[medio] > x) { return busquedaBinaria(A, x, i, medio - 1); } else { return medio + 1; } } } Commented el 25 sept. 2019 a las 1:09

1 respuesta 1

0

A la hora de detenerse en tu busquedaBinaria() en el caso de que no lo encuentra (el limite inferior es mas grande que el superior)

if (i > j) {
   return 0;
}

Estas devolviendo 0, la cual es la primer posicion del arreglo. Tendrias que devolver una posicion que no existe por ejemplo -1, luego a la hora de controlar que el elemento se encuentra en el arreglo te cercioras de que sea distinto a -1. En cuanto a esta sección de codigo:

  if(f.busquedaBinaria(A, x, 0, n)>=n){
      System.out.println("El numero no se encontro");
  }else{
      System.out.println("La posicion del numero fue: ");
      System.out.println(f.busquedaBinaria(A, x, 0, n));
  }

Seria mas eficiente realizar la busqueda binaria y guardar el resultado en una variable:

int resultado = f.busquedaBinaria(A, x, 0, n);
if(f.busquedaBinaria(A, x, 0, n) != -1){
   System.out.println("El numero no se encontro");
}else{
   System.out.println("La posicion del numero fue: " + resultado);
}

Ya que cuando imprimes la posición en el else nuevamente estas buscando un elemento que en teoria ya encontraste.

1
  • Por cierto, te recomendaria usar nombres de variables mas significativos, porque i,j,x,z no dicen mucho, si utilizaras nombres como limInf, limSup, etc. Seria mucho mas legible Commented el 26 sept. 2019 a las 5:14

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.