#include "sortui.h"

/*!
 * \file        buscabinaria.c
 * \brief       função para busca binária e contar a quantidade de comparções usadas na busca
 *
 * \date        30/05/2012 17:56:00
 * \version     0.0.1
 * \author      Alessandro Elias, ae11@inf.ufpr.br
 * \author      Ruanito Diego Santos, rds11@inf.ufpr.br
 */

/*!
 * \brief   Algoritmo de busca binária.
 *
 * \param   [in] value - valor a ser pesquisado.
 * \param   [in] pArray - ponteiro para o vetor a ser
 *          pesquisado.
 * \param   [in] size - número de elementos em pArray.
 * \param   [out] ncomp - ponteiro para a variável onde será
 *          atribuido o número de comparações feitas para
 *          encontrar value.
 *
 * \return  Índice de value dentro do vetor apontado por pArray.
 */
int binary_search(int value, const int *pArray, int size, int *ncomp)
{
    int high, low, mid;
    int found;

    high = size;
    found = low = 0;
    *ncomp = 0;
    do {
        mid = (low + high) / 2;             /* obtenha índice da metade do vetor. */
        if( value == *(pArray+mid) )        /* encontrou elemento? */
            found = 1;
        else if( value < *(pArray+mid) )    /* elemento esta a esquerda do meio? */
            high = mid - 1;
        else                                /* elemento esta a direita do elemento. */
            low = mid + 1;
        (*ncomp)++;                         /* conte o número de comparações. */
    } while( ! found && low <= high );

    return( found ? mid : -1 );             /* -1 elemento não encontrado, caso contrário índice do elemento. */
}/* binary_search */