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.