infoarena

Trebuie sa scrii o functie care sa caute un element de tipul int intr-un array de elemente de tipul int (in C++). Trebuie sa faci functia sa mearga indiferent daca sirul este sortat sau nu. Poti scrie o functie care sa indeplineasca conditiile de pana acum si care sa ia O(log n) atunci cand sirul este sortat? De preferat e ca functia sa fie O(n) atunci cand sirul nu este sortat.
L.E.: Daca nu se poate, demonstrati acest lucru. Care este cea mai buna complexitate care poate fi gasita pe cazul cand sirul e sortat fara sa stim de la bun inceput daca sirul e sortat sau nu?

Nu se poate sa presupui ca sirul e sortat si sa cauti binar ? Adica atat timp cat a[ left ]<=a[ mid ]<=a[ right ] caut binar. Cand conditia nu mai e respectata ma opresc si il caut liniar. Bine ca probabil in cel mai defavorabil caz o sa fie O(n+logn) dar nu se aproximeaza la O(n) ?

1 7 3 4 5 6 8 8 9 10

Ia incearca sa cauti elementul 7 in acest array.

?

Mda mi-am dat si eu seama de asta. Dar daca stii sigur ca elementul ala se afla in vector il poti cauta apoi liniar. Oricum e clar ca nu e o abordare buna :))

atunci cand vectorul e sortat crescator e cautare binara, se intra doar pe cate una dintre cele 2 ramuri, cu conditia ca elementul sa si existe in vector
in cazul cel mai defavorabil la fiecare apel al functiei se analizeaza exact un element din vector => O(N)

Smecher!  =D&gt;