Vector bicreixent P99753

En aquest problema, diem que un vector de $n$ nombres enters @v[0..@$n-1$@]@ és bicreixent si $n \ge 2$, @v[0]@ $>$ @v[@$n-1$@]@, i existeix un índex $j$ entre $0$ i $n-2$ que satisfà:

• @v[0]@ $\le \ldots \le$ @v[@$j-1$@]@ $\le$ @v[@$j$@]@,

• @v[@$j+1$@]@ $\le$ @v[@$j+2$@]@ $\le \ldots \le$ @v[@$n-1$@]@.

Per exemple, el vector @[12, 12, 15, 20, 1, 3, 3, 5, 9]@ és bicreixent (amb $j = 3$).

Implementeu una funció eficient

    bool search(int x, const vector<int>& v);

que, donats un enter @x@ i un vector bicreixent @v@, retorni si @x@ apareix a @v@ o no. Podeu usar i implementar funcions auxiliars si us calen.

Precondició

El vector @v@ és bicreixent.

Observació

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