Question

Se citeşte un număr natural n, si cele n elemente reale, distincte, odonate crescător, ale unui tablou unidimensional, x.Se citesc, deasemenea, doua numere, a si b. Sa se afiseze numarul elementelor din vectorul x, care se afla in intervalul inchis determinat de valorile lui a si b([a,b] dacă a<b sau [b,a] daca b<=a). Se va alege un algoritm eficient din punct de vedere al timpului de executare.

Answer 1

Fie nr numarul cerut. Algoritmul:
Fie maxx=cel mai mare elem din x si minx cel mai mic elem din x (asa le-am notat - nu le calculezi!)
1) faci cautare binara a lui a in vectorul x - vei obtine cel mai mic indice  i, pt care x[i]>=a. Se disting cazurile:
      a)  a<minx =>i=1; 
      b)  a>maxx => nu avem i, rezultatul: nr=0;
      c) minx<=a<=maxx  -> 1<=i<=n
 2)  faci cautare binara a lui b in vectorul x - vei obtine cel mai mare indice  j, pt care x[j]<=b. Se disting cazurile:
      a) b>maxx -> j=n
      b) b<minx- >nu avem j -> nr=0
      c) minx<=b<=maxx - > 1<=j<=n  
Daca la 1) si 2) obtii a) sau b), solutia: nr=j-i+1, altfel (daca la 1) sau 2) te afli in subcazul c)),  nr=0.