The code:
#include <iostream>
using namespace std;
class ListaOrdenada {
private:
int * items;
int tamanho, capacidade;
public:
ListaOrdenada(int cap) {
this->capacidade = cap;
this->tamanho = 0;
items = new int[cap];
}
~ListaOrdenada() {
delete [] items;
}
void insere(int key) {
if (tamanho < capacidade) {
int i = 0;
while (key < items[i] and i <= tamanho) {
i++;
}
int j = capacidade-1;
for (; j > i; j--) {
items[j] = items[j+1];
}
items[i] = key;
}
}
int buscaSequencial(int key) {
int i = 0;
while (i <= tamanho) {
if (items[i] == key) {
return i;
}
i++;
}
return -1;
}
int buscaBinaria(int item) {
return buscaBinaria(0, tamanho - 1, item);
}
int valida() {
for (int i = 0; i < tamanho - 1; i++) {
if (items[i] > items[i + 1]) return 0;
}
return 1;
}
void exibe() {
for (int i = 0; i < tamanho; i++) {
cout << i << ": " << items[i] << "; ";
}
cout << endl;
}
private:
int buscaBinaria(int inicio, int final, int item) {
int meio = (inicio + final)/2;
if (items[meio] == item) {
return meio;
}
else if (items[meio] > item) {
return buscaBinaria(inicio, meio, item);
}
else {
return buscaBinaria(meio, final, item);
}
}
};
int main () {
ListaOrdenada lista(10);
int elementos [] = {10, 5, 25, 1, 5, 13, 50, 99, 33, 12};
for (int i = 0; i < 10; i++) {
lista.insere(elementos[i]);
}
cout << "Lista valida: " << (lista.valida()?"sim":"nao") << endl;
lista.exibe();
int teste [] = {5, 7, 16, 99, 45, 12, 33, 1, 60, 6};
for (int i = 0; i < 10; i++) {
cout << "Buscando " << teste[i] << ": sequencial = " << lista.buscaSequencial(teste[i]) << " binaria = " << lista.buscaBinaria(teste[i]) << endl;
}
}