algorithm - What is the time complexity for finding the maximum value less than a given value? -

any data structure know of orders data, has, @ best, o(log n) lookup.

i argue find maximum value less given value, need first discover given value live in data structure. (i have no proof required first step).

that requires o(log n) time.

from there, need find maximum value less that. in case of array, 1 index o(1). in case of balanced tree, traverse path typically o(log n).

in case, seems average total time complexity must o(log n).

is correct, or can somehow better?

no, there no more efficient comparisons based algorithm. worst case indeed bounded omega(logn) using comparisons based algorithms, since there n possible outputs (all of them can achieved given correct query), , choose 1 of them computation tree must of height log(n). gives lower bound of omega(logn) problem using comparisons, regardless of data structure used.

this bound tight, since in sorted array, 1 can find desired value using binary search in o(logn).