Ordered List Logic Error (C++)

Question

In the discipline of data structure, the teacher gave us a cpp code with an ordered list and asked us to implement the methods of binary search, sequential search and insertion, but I’m not able to identify why the program runs but the output is not expected (ends by returning 1). I’ve tried debugging, but I’m not very experienced at it yet.

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;

    }

} 

Answer 1

There are several errors in your code. I fixed the function inserts and put some comments.

    void insere(int key) {
        if (tamanho < capacidade) {
            int i = 0;
            // primeiro tem que garantir que a posição é válida (i < tamanho)        
            // se quiser a lista ordenada de forma crescente, 
            //você deve inserir quando (key > items[i]) for falso
            while (i < tamanho and key > items[i]) { 
                i++;
            } // i está na posição em que será feita a inserção ou no final da lista (i == tamanho)
            int j = tamanho; // j é o tamanho da lista
            for (; j >= i; j--) { 
                items[j + 1] = items[j]; // desloca os elementos 
            }
            items[i] = key;
            tamanho += 1; // Aumenta o tamanho da lista após inserir
        }

    }

To debug you can put some prints in the middle of the code to check if the value of a variable is in the value you expect it to be. For example:

for (int i = 0; i < 10; i++) {
    lista.insere(elementos[i]);
    // Imprime a lista para ver se está inserindo corretamente
    lista.exibe();
}