digitalmars.D.bugs - [Issue 15385] New: Apply Andersson91 idea to SortedRange.contains
- via Digitalmars-d-bugs (21/21) Nov 28 2015 https://issues.dlang.org/show_bug.cgi?id=15385
https://issues.dlang.org/show_bug.cgi?id=15385 Issue ID: 15385 Summary: Apply Andersson91 idea to SortedRange.contains Product: D Version: D2 Hardware: All OS: All Status: NEW Severity: enhancement Priority: P1 Component: phobos Assignee: nobody puremagic.com Reporter: andrei erdani.com http://user.it.uu.se/~arnea/ps/searchproc.pdf describes a simple trick that reduces the number of comparisons in a binary search. The same idea can be used for binary search in an array. The idea is to save an index (not a node as described in the paper). In https://github.com/D-Programming-Language/phobos/blob/master/std/range/package.d#L7833 the routine could do only one evaluation of predFun and then continue searching. Only when the count goes down to zero is the other comparison done. --
Nov 28 2015