Primera aparició en vector quasi ordenat X48505


Statement
 

pdf   zip   main.cc

html

Escriviu una funció eficient


int first_occurrence(double x, const vector<double>& v);


que retorni la posició de la primera aparició de x dins del vector v. Si x no apareix a v, retorneu un -1.

Precondició

El vector v està “quasi ordenat” en ordre no decreixent, en el sentit que hi pot haver com a molt un parell d’índexos i i j tals que 0 ≤ i < j < n i v[i] > v[j].

Observació Podeu definir funcions auxiliars si us calen.

Observació Només cal enviar el procediment demanat; el programa principal serà ignorat.

Observació Feu servir l’arxiu main.cc que us donem. Conté el procediment principal que llegeix el joc de proves, crida a la funció que us demanem implementar, i escriu el resultat en el format esperat.

Per a la vostra informació, un joc de proves consta de diversos casos. Cada cas comença amb un natural n ≥ 0, seguit dels n doubles que formen el vector v. A continuació apareix un natural c ≥ 0, seguit de c doubles pels quals volem conèixer quina és la seva primera aparició a v.

Public test cases

  • Input

    7
1 2 2 3 2 3 4
7
0 1 2 2.5 3 4 5

6
1 2 2 3 3 4
7
0 1 2 2.5 3 4 5

    Output

    -1
0
1
-1
3
6
-1
-1
0
1
-1
3
5
-1
    • Information
    Author
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++