passing predicates to lowerBound, or alternatively, how lazy is map?

[John Colvin via Digitalmars-d-learn]

On Wednesday, 11 June 2014 at 11:38:07 UTC, Andrew Brown wrote:
>>>
>>> My question about this is how lazy is map? Will it work on 
>>> every value of order and then pass it to lowerBound, or could 
>>> it work to evaluate only those values asked by lowerBound? I 
>>> guess probably not, but could a function be composed that 
>>> worked in this way?
>>>
>>> Thank you very much
>>>
>>> Andrew
>>
>> map is fully lazy.
>>
>> However, if you've already got the sorted indices in `order`, 
>> I would do this:
>>
>> auto numLessThanN = numbers.indexed(order).countUntil!((x) => x
>> >= N)();
>
> Thanks for the reply, I'm going to have a lot of numbers 
> though. I guess compared to the time it will take me to sort 
> them, it makes no difference, but is it right that countUntil 
> will take linear time? If I can figure out lowerBound, then I 
> have my answer in log(n) time?
>
> Best
>
> Andrew

You are correct. assumeSorted and lowerBound will provide better 
time complexity than countUntil