Zestaw C ++: liczenie elementów mniejszych niż wartość
Zakładając, że mam STLset <int> s
i anint x
, jak mogę policzyć liczbę elementóws
mniej niżx
?
SzukamO(log n)
(lub podobne; wszystko, co jest znacznie lepsze niżO(n)
) rozwiązanie;
Już o tym wiemstd::distance(s.begin(), s.lower_bound(x))
, ale toO(n)
, Wierzę, ponieważset
s nie są przypadkowe.