Vectorized searches complexity

What is the time complexity of thrust::lower_bound in the RLE https://github.com/thrust/thrust/blob/master/examples/run_length_decoding.cu#L42 Thrust example?
Is it linear in values_last - values_first and logarithmic in last - first?
Can it benefit from sorted values input?