// Lab14.java  (C) 2012 adolfo@di-mare.com

import java.util.Random;

/** \file  Lab14.java
    \brief Búqueda lineal y binaria en un vector ordenado.

    \author Adolfo Di Mare <adolfo@di-mare.com>
    \date   2012
*/

class Lab14 {

    /** Busca en el vector \c A[] el valor \c "llave" y retorna su posición.
        <ul><li> Si no lo encuentra, retorna un número negativo.
        <li> Busca en el rango \c A[izq..der].
        <li> La búsqueda se hace secuencialmente. </ul>
    */
    public static int busquedaLineal( int A[], int llave, int izq, int der, int N ) {
        grabeRenglon( A, izq, der, der, N );
        for ( int n = izq; n <= der; n++ ) {
            if ( A[n] == llave ) {  // encontró la llave
                return n;
            }
        }
        return -1;   // no encontró la llave
    }

    /** Busca en el vector \c A[] el valor \c "llave" y retorna su posición.
        - Si no lo encuentra, retorna un número negativo.
        - Busca en el rango \c A[izq..der].
        - Usa búsqueda binaria.
    */
    public static int busquedaBinaria( int A[], int llave, int izq, int der, int N ) {
        while ( izq <= der ) {
            int medio = ( izq + der ) / 2;

            grabeRenglon( A, izq, medio, der, N );

            if ( llave == A[medio] ) {  // encontró la llave
                return medio;
            }
            else if ( llave < A[medio] ) {
                der = medio - 1;        // busca a la izquierda en A[]
            }
            else {
                izq = medio + 1;        // busca a la derecha en A[]
            }
        }
        return -1;   // no encontró la llave
    }


    /// Pone los números de índice \c [0..N] para ver los valores del vector.
    public static void grabaEncabezado( int N ) {
        for ( int i = 0; i < N; i++ ) {
            System.out.print( String.format("%3d",i) + " ");
        }
        System.out.print("\n");

        for ( int i = 1; i <= 4 * N; i++ ) {
            System.out.print('-');
        }
        System.out.print("\n");
    }

    /// Graba en \c cout una parte del vector \c A[].
    /// - Los índices que grabados son los del rango \c A[izq..der].
    /// - Marca con una estrillita \c "*" el valor \c "A[mid]".
    public static void grabeRenglon( int A[], int izq, int mid, int der, int N ) {
        for ( int i = 0; i < N; i++ ) {
            if ( i < izq || i > der ) {
                System.out.print("    ");
            }
            else if ( i == mid ) {         // mark middle value
                System.out.print( String.format("%3d",A[i]) + "*");
            }
            else {
                System.out.print(String.format("%3d",A[i]) + " ");
            }
        }
        System.out.print("\n");
    }

    /// Graba en \c cout un mensaje de encontrado
    /// - Si <code> idx >= 0 </code> graba "encontrado".
    /// - Si <code> idx < 0 </code> graba "NO encontrado".
    public static void grabeEncontrado( int idx , int llave ) {
        System.out.print( "la llave " + (llave) );
        if ( idx >= 0 ) {
            System.out.print(" fue encontrada en la posición [" +(idx)+"]\n");
        }
        else {
            System.out.print(" no fue encontrada");
        }
    }

    /// Programa principal.
     public static void main( String args[] ) {
        final int N = 15;
        int A[], llave, idx, i; A = new int[N];

        // pone algunos valores en el vector
        for ( i=0; i < N; i++ ) {
            A[i] = 2 * i;
        }

        // busca varias veces un número en el vector
        Random rand = new Random( 1820 );
        for ( i=0; i<11; ++i ) {
            llave = rand.nextInt() % (2*N) ;

            System.out.print("\n\n");
            System.out.print("*** Búsqueda SECUENCIAL ***\n");
            grabaEncabezado( N );
            idx = busquedaLineal( A, llave, 0, N-1, N );
            grabeEncontrado( idx , llave );

            System.out.print("\n\n");

            System.out.print("*** Búsqueda BINARIA ***\n");
            grabaEncabezado( N );
            idx = busquedaBinaria( A, llave, 0, N-1, N );
            grabeEncontrado( idx , llave );
        }
        return;
    }
}

// EOF: Lab14.java