// Busca los n códigos de una lista de n estudiantes y cuenta las comparaciones.
// Uso: lookup n linear|binary
#include <cstdlib>
#include <iostream>
#include <string>
#include <vector>

// Devuelve el índice de code, o -1. Suma a comparisons cada elemento que mira.
long long linear_search(const std::vector<int>& codes, int code, long long& comparisons) {
    long long size = static_cast<long long>(codes.size());
    for (long long i = 0; i < size; i++) {
        comparisons++;
        if (codes[i] == code) {
            return i;
        }
    }
    return -1;
}

// Igual, pero exige que codes esté ordenado.
long long binary_search(const std::vector<int>& codes, int code, long long& comparisons) {
    long long low = 0;
    long long high = static_cast<long long>(codes.size()) - 1;
    while (low <= high) {
        long long middle = low + (high - low) / 2;
        comparisons++;
        if (codes[middle] == code) {
            return middle;
        }
        if (codes[middle] < code) {
            low = middle + 1;
        } else {
            high = middle - 1;
        }
    }
    return -1;
}

int main(int argc, char *argv[]) {
    if (argc != 3) {
        std::cerr << "uso: lookup n linear|binary\n";
        return 1;
    }
    int n = std::atoi(argv[1]);
    std::string mode = argv[2];

    std::vector<int> codes;
    for (int i = 0; i < n; i++) {
        codes.push_back(2 * i);
    }

    long long comparisons = 0;
    long long found = 0;
    for (int code : codes) {
        long long index = mode == "linear" ? linear_search(codes, code, comparisons)
                                           : binary_search(codes, code, comparisons);
        if (index >= 0) {
            found++;
        }
    }
    std::cout << "n = " << n << ", encontrados = " << found
              << ", comparaciones = " << comparisons << "\n";
    return 0;
}