Ad argvmentvm transi
Topos Uranos
Latine

Qvaerere et ordinare

Svmmarivm

Qvaerere et ordinare dvo svnt problemata fvndamentalia de collectionibvs, et inter ea commvtatio est: semel ordinare constat, sed omnem qvaesitionem posteriorem vilivs reddit. Lectio manv scribit qvaesitionem linearem et binariam, qvae in datis ordinatis dimidivm in qvoqve gradv reicit; binariam per invariantem svam ivstificat, eam terminari demonstrat, gyros eivs nvmerat et tres errores qvi eam pessvm dant stvdet. Seqvvntvr ordinatio per selectionem et per insertionem, cvm invariantibvs svis et accvrata nvmeratione comparationvm; deinde eadem problemata cvm bibliotheca intervallorvm, et ratio qvae decernit qvando expediat ante qvaesitionem ordinare.

Proposita discendi

  1. Qvaesitionem linearem et binariam implementare, et binariam per invariantem svam ivstificare («si valor adest, inter low et high est»), cvm demonstratione eam terminari.
  2. Ordinationem per selectionem et per insertionem implementare, invariantem vtrivsqve envntiare et comparationes earvm in casv optimo et in casv pessimo nvmerare.
  3. std::ranges::sort, std::ranges::contains, std::ranges::find, std::ranges::binary_search et std::ranges::lower_bound loco versionvm propriarvm adhibere, cvm res postvlat, praecondiciones earvm servando.
  4. Pro nvmero qvaesitionvm praevisarvm decernere vtrvm expediat data ante qvaesitionem ordinare, et decisionem nvmeratione comparationvm ivstificare.

Qvaesitio linearis

Qvaerere est respondere, data collectione et valore, vtrvm valor adsit et vbi. Sine notitia de ordine datorvm, nvlla alia ratio est qvam ea singvla inspicere: haec est qvaesitio linearis. Cvm valor non adest, hic cvrsvs values.size() reddit, primam positionem qvae ad vectorem non pertinet: index validvs non est, ita vt cvm responso non confvndatvr, et eadem conventio est qvam bibliotheca seqvitvr, vt in qvinta sectione videbitvr.

Programma in C++
#include <cstddef>#include <print>#include <vector>​// Praecondicio: nvlla.// Postcondicio: reddit minimvm indicem i cvm values[i] == target,// vel values.size(), si target non adest.std::size_t linearSearch(const std::vector<int>& values, int target){    // Invarians: target non est in 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("{}: non adest", target);        } else {            std::println("{}: positio {}", target, pos);        }    }}
Exitvs
207: positio 3112: positio 1999: non adest

Invarians versvs 10 rectitvdinem praebet. Initio, cvm i aeqvalis est 0, aliqvid de tractv vacvo affirmat et vera est. Si initio gyri valet et values[i] non est valor qvaesitvs, in fine eivs valet cvm vno elemento plvs. Iam vero circvitvs dvos exitvs habet: si return i; exseqvitvr, values[i] est valor qvaesitvs et, per invariantem, nvllvm elementvm anterivs erat, vnde i est prima occvrrentia (qvam ob rem 112, qvi bis apparet, in positione 1 nvntiatvr); si circvitvs per condicionem terminatvr, i valet values.size() et invarians dicit valorem nvsqvam esse. return intra circvitvm fvnctionem terminat, et cvm ea circvitvm, et vexillvm parcit.

Svmptvs, eo sensv qvo lectio Svmptvs algorithmi eam vocem adhibet, comparationibvs values[i] == target metitvr. Si valor non adest, accvrate nn fivnt, vna pro qvoqve elemento: casvs pessimvs. Si in positione pp est, p+1p + 1 fivnt. Qvaesitio linearis est igitvr O(n)O(n): cvm dvplo datorvm, dvplvm laboris. Sine notitia additicia melivs fieri non potest: algorithmvs qvi vnvm elementvm inspicere omitteret nesciret vtrvm valor ibi esset.