Saltar al contenido
Topos Uranos
Español

Buscar y ordenar

Resumen

Buscar y ordenar son los dos problemas fundamentales sobre colecciones, y entre ellos hay un intercambio: ordenar una vez cuesta, pero abarata cada búsqueda posterior. La clase escribe a mano la búsqueda lineal y la binaria, que sobre datos ordenados descarta la mitad en cada paso; justifica la binaria con su invariante, prueba que termina, cuenta sus vueltas y estudia los tres errores que la arruinan. Siguen los ordenamientos por selección y por inserción, con sus invariantes y el conteo exacto de sus comparaciones; después, los mismos problemas con la biblioteca de rangos, y la cuenta que decide cuándo conviene ordenar antes de buscar.

Objetivos de aprendizaje

  1. Implementar la búsqueda lineal y la binaria, y justificar la binaria con su invariante («si el valor está, está entre low y high»), con la prueba de que termina.
  2. Implementar el ordenamiento por selección y por inserción, enunciar el invariante de cada uno y contar sus comparaciones en el mejor y en el peor caso.
  3. Usar std::ranges::sort, std::ranges::contains, std::ranges::find, std::ranges::binary_search y std::ranges::lower_bound en lugar de las versiones propias cuando corresponda, respetando sus precondiciones.
  4. Decidir, según el número de búsquedas previstas, si conviene ordenar los datos antes de buscar en ellos, y justificar la decisión con el conteo de comparaciones.

Búsqueda lineal

Buscar es responder, dada una colección y un valor, si el valor está y dónde. Sin información sobre el orden de los datos, no hay más estrategia que mirarlos uno por uno: es la búsqueda lineal. Cuando el valor no está, este curso devuelve values.size(), la primera posición que no pertenece al vector: no es un índice válido, de modo que no se confunde con una respuesta, y es la misma convención que sigue la biblioteca, como se verá en la quinta sección.

Programa en C++
#include <cstddef>#include <print>#include <vector>​// Poscondición: devuelve el menor índice i con values[i] == target,// o values.size() si target no está.std::size_t linearSearch(const std::vector<int>& values, int target){    // Invariante: target no está en values[0], ..., values[i - 1].    for (std::size_t i{0}; i < values.size(); ++i) {        if (values[i] == target) {            return i;        }    }    return values.size();}​int main(){    const std::vector<int> codes{405, 112, 318, 207, 112, 530};    for (const int target : {207, 112, 999}) {        const std::size_t pos{linearSearch(codes, target)};        if (pos == codes.size()) {            std::println("{}: no está", target);        } else {            std::println("{}: posición {}", target, pos);        }    }}
Salida
207: posición 3112: posición 1999: no está

El invariante de la línea 9 da la corrección. Al comenzar, con i igual a 0, afirma algo sobre un tramo vacío y es verdadero. Si vale al comenzar una vuelta y values[i] no es el buscado, vale al terminarla con un elemento más. Ahora bien, el bucle tiene dos salidas: si return i; se ejecuta, values[i] es el buscado y, por el invariante, ningún elemento anterior lo era, de donde i es la primera aparición (por eso el 112, que aparece dos veces, se informa en la posición 1); si el bucle termina por la condición, i vale values.size() y el invariante dice que el valor no está en ninguna parte. El return dentro del bucle termina la función, y con ella el bucle, y ahorra una bandera.

El costo, en el sentido de la clase El costo de un algoritmo, se mide por las comparaciones values[i] == target. Si el valor no está, se hacen exactamente nn, una por elemento: el peor caso. Si está en la posición pp, se hacen p+1p + 1. La búsqueda lineal es, entonces, O(n)O(n): con el doble de datos, el doble de trabajo. Sin información adicional no puede hacerse mejor: un algoritmo que dejara de mirar un elemento no sabría si el valor estaba allí.