Cautare binara sau liniara?

[•MciprianM]

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?

[•soriyn]

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) ?

[•maritim]

1 7 3 4 5 6 8 8 9 10

Ia incearca sa cauti elementul 7 in acest array.

?

[•soriyn]

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 )

[•Vman]

Cod:

int cauta(int st, int dr)
{
 if (st == dr)
 {
  if (A[st] == who) return st;
  return -1;
 }

 int m = (st + dr) >> 1;
 if (A[m] == who) return m;
 
 int v = -1;
 if (A[m] < who)
 {
  if (m != st) v = cauta(st, m-1);
  if (v == -1) v = cauta(m+1, dr);
 }
 else
 {
  v = cauta(m+1, dr);
  if (v == -1 && m != st) v = cauta(st, m-1);
 }

 return v;
}

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)

[•MciprianM]

Smecher!