DICTOMICA

2. Cerca dicotòmica
Enunciat: Feu una funció
int posicio(double x, const vector<double>& v, int esq, int dre);
que retorni la posició on es troba x dins del subvector v[esq..dre] . Si x no apareix a v[esq..dre] o
esq > dre , cal retornar -1 .
Podem suposar que
• El vector v està ordenat creixentment.
• Inicialment (0 <= esq) and (dre < v.size()) .
Nota: En canvi, esq <= dre pot no ser cert ni al principi: Penseu quina crida faríeu per ordenar una taula
de mida 0.


Solució recursiva:
// Pre: (0 <= esq) and (dre < v.size()) and (v esta ordenat creixentment)
// Post: retorna i tal que, o be esq<=i<=dre i v[i]==x, o be i==-1 i x no es a v[esq..dre]
int posicio(double x, const vector<double>& v, int esq, int dre) {
if (esq > dre) return -1;
int pos = (esq + dre)/2;
// posicio central de v[esq..dre]
if (x < v[pos]) return posicio(x, v, esq, pos - 1);
if (x > v[pos]) return posicio(x, v, pos + 1, dre);
return pos;
}


Solució iterativa:
// Pre: (0 <= esq) and (dre < v.size()) and (v esta ordenat creixentment)
// Post: retorna i tal que, o be esq<=i<=dre i v[i]==x, o be i==-1 i x no es a v[esq..dre]
int posicio(double x, const vector<double>& v, int esq, int dre) {
int pos;
bool trobat = false;
// Inv: (0 <= esq), (dre < v.size()),
// si x es a v[E..D], llavors es a v[esq..dre]
// on E i D son els valors inicials d'esq i dre,
// i a mes trobat indica que hem trobat x a pos
while (not trobat and esq <= dre) {
pos = (esq + dre)/2;
// posicio central de v[esq..dre]
if (x < v[pos]) dre = pos - 1;
else if (x > v[pos]) esq = pos + 1;
else trobat = true;
}
if (trobat) return pos;
else return -1;
}