www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 15385] New: Apply Andersson91 idea to SortedRange.contains


          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


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