• via Digitalmars-d-bugs (21/21) Nov 28 2015 https://issues.dlang.org/show_bug.cgi?id=15385

via Digitalmars-d-bugs <digitalmars-d-bugs puremagic.com> writes:

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.

--