<div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Wed, Mar 18, 2015 at 2:49 PM, martin <span dir="ltr"><<a href="mailto:martin.drautzburg@web.de" target="_blank">martin.drautzburg@web.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><br>
I want to find the lowest element in a collection of items which is greatet or equal to a given element. There can be<br>
more than one such element in which case I wouldn't care which one I get. I still want to be able to iterate over the<br>
elements following the found element. In a way I want the equivalent of<br>
<br>
select ...<br>
from table<br>
where table.x > n<br>
<br>
<br>
How would I do this efficiently?<br>
<br>
I tried using an ordered list, but I would still have to traverse half the list on average.<br></blockquote><div><br></div><div>You could do it in log time (using a binary search algorithm) with an ordered Vector or Array. Lists are not an appropriate data structure for random access.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">
I suppose I can do this with some sort of tree, but i don't want to write all the code myself. But I couldn't find<br>
anything off the shelf.<br></blockquote><div><br></div><div>Data.Map supports that operation in log time with splitLookup. You can use the values of the map to count the occurrences of a given element. If all of the elements are unique you can save a bit of space and use Data.Set instead, which has a splitMember function.</div><div><br></div><div>-bob</div><div><br></div></div></div></div>