uiua icon indicating copy to clipboard operation
uiua copied to clipboard

Introduce bisection primitive

Open tmpr opened this issue 6 months ago • 2 comments

I would appreciate some dyadic primitive which accepts as a first argument a sorted array and computes the second argument's rank in the first array in logarithmic time using binary search, similar to BQN bins.

tmpr avatar Jun 12 '25 10:06 tmpr

Bins is non-trivial to implement yourself, but I can't remember a time when I've actually needed it. Do you have an example?

kaikalii avatar Jul 02 '25 02:07 kaikalii

I was trying to implement interval-trees in Uiua (I also wrote a blog-post about it.) -- a tldr is that I would like to be able to take elements up to a certain index from a sorted array, but doing so using do is rather slow. Either some version of a takewhile (which I propose in #709) or a binsearch would do help there.

tmpr avatar Jul 02 '25 06:07 tmpr