Código de Java - Búsqueda dicotómica en una tabla, de forma recursiva

Imágen de perfil

Búsqueda dicotómica en una tabla, de forma recursivagráfica de visualizaciones


Java

Publicado el 13 de Noviembre del 2018 por Administrador
961 visualizaciones desde el 13 de Noviembre del 2018
Ejemplo de búsqueda dicotómica en una tabla, de forma recursiva.

Código 35 del libro Ejercicios de Programación en Java

Versión 1

Publicado el 13 de Noviembre del 2018gráfica de visualizaciones de la versión: Versión 1
962 visualizaciones desde el 13 de Noviembre del 2018
estrellaestrellaestrellaestrellaestrella
estrellaestrellaestrellaestrella
estrellaestrellaestrella
estrellaestrella
estrella

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
import java.io.*;
 
public class Main {
 
    // a la función se le pasa, la tabla, el elemento a buscar, y la primera
    // y última posición donde buscar.
    static int busca (int t[], int elem, int primero, int ultimo) {
        int pos;
        if(primero >= ultimo) // caso base: solo hay un elemento donde buscar
            if (t[primero]==elem)
                pos =primero;
            else
                pos =-1;
        else
        {
            int pos1, pos2;
            // llamada recursiva
            //buscamos en la primera mitad de la tabla: 0..mitad
            pos1 = busca (t, elem, primero, (primero+ultimo)/2);
            // buscamos en la segunda parte de la tabla: mitad+1..ultimo
            // se pone mitad+1, por que el elemento mitad ya pertenece a la
            // primera parte... por no repetirlo
            pos2 = busca (t, elem, (primero+ultimo)/2+1, ultimo);
            if (pos1 != -1) // si lo encuentro en la primera parte
            pos =pos1;
            else
            pos =pos2; // en caso contrario debo encontrarlo en la segunda parte
            // en caso de no encontrarse pos1 y pos2 serán -1, y se cogerá el valor de pos2 (-1)
        }
        return(pos);
    }
 
    // el usuario utilizará esta función por comodidad
    // solo es necesario pasarle la tabla y el elemento a buscar
    // devuelve el índice del elemento si lo encuentra o -1 en caso contrario
    static int busca (int t[], int elem)
    {
        return (busca (t, elem, 0, t.length-1));
    }
 
    public static void main(String[] args) {
        int datos[];
        int num;
        int pos;
        datos = new int[10];
        // para no teclearlos, cagamos datos aleatorios
        for (int i = 0; i < datos.length; i++)
        datos[i] = (int) (Math.random()*1000+1);
        System.out.println("Los datos son:");
        for (int i = 0; i < datos.length; i++)
        System.out.print(datos[i] + " ");
        System.out.print("\n\nElemento a buscar: ");
        num=entero();
        // llamamos a la función buscar
        pos=busca(datos, num);
        if (pos == -1)
            System.out.println("\n\nNo encontrado");
        else
            System.out.println("\n\nEncontrado en la posición: " +pos);
    }
 
    static int entero(){
        int valor=Integer.parseInt(inicializar());
        return valor;
    }
 
    static String inicializar(){
        String buzon="";
        InputStreamReader flujo=new InputStreamReader(System.in);
        BufferedReader teclado=new BufferedReader(flujo);
        try{
            buzon=teclado.readLine();
        }
        catch(Exception e){
            System.out.append("Entrada incorrecta)");
        }
        return buzon;
    }
}



Comentarios sobre la versión: Versión 1 (0)


No hay comentarios
 

Comentar la versión: Versión 1

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios
Es necesario revisar y aceptar las políticas de privacidad

http://lwp-l.com/s4921