// lab14.cpp  (C) 2005 adolfo@di-mare.com

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

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

#include <iostream> // cout
#include <iomanip>  // setw()

// En los prototipos C++ no exige poner los nombres de los parámetros
int busquedaBinaria( const int [], int, int, int, int );
int busquedaLineal(  const int [], int, int, int, int );

void grabaEncabezado( int );
void grabeRenglon( const int [], int, int, int, int );

/** 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].
    - La búsqueda se hace secuencialmente.
*/
int busquedaLineal( const 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.
*/
int busquedaBinaria( const 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.
void grabaEncabezado( int N ) {
    for ( int i = 0; i < N; i++ ) {
        cout << setw( 3 ) << i << ' ';
    }

    cout << endl;

    for ( i = 1; i <= 4 * N; i++ ) {
        cout << '-';
    }

    cout << endl;
}

/// 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]".
void grabeRenglon( const int A[], int izq, int mid, int der, int N ) {
    for ( int i = 0; i < N; i++ ) {
        if ( i < izq || i > der ) {
            cout << "    ";
        }
        else if ( i == mid ) {         // mark middle value
            cout << setw( 3 ) << A[i] << '*';
        }
        else {
            cout << setw( 3 ) << A[i] << ' ';
        }
    }

   cout << endl;
}

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

#include <stdlib.h>   // srand() && rand()

/// Programa principal.
int main() {
    const int N = 15;
    int A[N], llave, idx, i;

    // 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
    srand( 1820 );
    for ( i=0; i<11; ++i ) {
        llave = rand() % (2*N) ;

        cout << endl << endl;
        cout << "*** Búsqueda SECUENCIAL ***" << endl;
        grabaEncabezado( N );
        idx = busquedaLineal( A, llave, 0, N-1, N );
        grabeEncontrado( idx , llave );

        cout << endl << endl;

        cout << "*** Búsqueda BINARIA ***" << endl;
        grabaEncabezado( N );
        idx = busquedaBinaria( A, llave, 0, N-1, N );
        grabeEncontrado( idx , llave );

    }
    return 0;
}

// EOF: lab14.cpp