# include <malloc.h>
# include <stdio.h>
# include <stdlib.h>
# include <conio.h>

typedef int TIPOCHAVE;

# define MAX 10

typedef struct {
        TIPOCHAVE chave;
} REGISTRO;

typedef struct {
        REGISTRO A[MAX];
        int nElem;
} LISTA;

bool inicializaLista(LISTA *l) {
     l->nElem = 0;
     int i;
     for(i = 0; i < MAX; i++){
            l->A[i].chave = i;
            l->nElem++;
     }
     return (true);
}

bool printaLista(LISTA l){
     int i = 0;
     for(i; i < l.nElem; i++) {
            printf("%i ", l.A[i].chave);
     }
     return (true);
}

bool insere(LISTA *l, int i, TIPOCHAVE ch) {
     if((i > (l->nElem)) || i < 0 || (l->nElem >= MAX)) {
           printf("\nErro");
           return (false); //posição incorreta ou lista cheia
     }
     if((l->nElem > 0) && (i < l->nElem)) {
                 int j;
                 for(j = l->nElem; j >= (j + i); j--){
                     l->A[j] = l->A[j-1];
                 }
     }
     l->A[i].chave = ch;
     l->nElem++;
     return(true);
}

int busca(LISTA l, TIPOCHAVE ch) {
    if(l.nElem == 0) return(-1);
    int i = 0;
    while(i < l.nElem) {
            if(l.A[i].chave == ch) return(i);
            else i++;
    }
    return (-1);
}

int buscaBin(LISTA l, TIPOCHAVE ch){
    if(l.nElem == 0) return(-1);
    int inf, sup, meio;
    inf = 0;
    sup = l.nElem;
    while(inf <= sup){
              meio = (inf + sup)/2;
              if(l.A[meio].chave == ch) return (meio);
              else if(l.A[meio].chave > ch) { //vai para esquerda
                   sup = meio -1;
              }
              else { //vai para a direita
                   inf = meio + 1;
              }
    }
    return (-1); // não achou;
}

int main() {
    LISTA lista;
    inicializaLista(&lista);
    printaLista(lista);
    //insere(&lista, 1, 6);
    //printf("\nlista printada:\n");
    //printaLista(lista);
    //int index = busca(lista, 6);
    //printf("\nPosicao da chave busca eh %i \n", index);
    int index = buscaBin(lista, 5);
    printf("\nPosicao da chave usando busca binaria eh %i \n", index);
    system("pause");
}