On Wednesday, 11 June 2014 at 11:22:08 UTC, Andrew Brown wrote:
Hi there,
The problem this question is about is now solved, by writing my
own binary search algorithm, but I'd like to ask it anyway as I
think I could learn a lot from the answers.
The problem was, given an array of numbers, double[] numbers,
and an ordering from makeIndex size_t[] order, I want to count
how many numbers are less than a number N. The obvious way
would be to use lowerBound from std.range, but I can't work out
how to pass it a predicate like "numbers[a] < b". Could someone
explain the template:
(SearchPolicy sp = SearchPolicy.binarySearch, V)(V value) if
(isTwoWayCompatible!(predFun, ElementType!Range, V));
The alternative way I thought to do it was to combine map with
lowerBound, i.e.:
map!(a => numbers[a])(order).assumeSorted
.lowerBound(N)
.length
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)();
