• via Digitalmars-d-bugs (54/54) May 18 2014 https://issues.dlang.org/show_bug.cgi?id=12762

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

https://issues.dlang.org/show_bug.cgi?id=12762

          Issue ID: 12762
           Summary: Missing documentation for
                    std.range.SearchPolicy.linear
           Product: D
           Version: D2
          Hardware: All
                OS: All
            Status: NEW
          Severity: minor
          Priority: P1
         Component: websites
          Assignee: nobody puremagic.com
          Reporter: bearophile_hugs eml.cc

In this page:
http://dlang.org/phobos/std_range.html#SearchPolicy


The documentation about the enum std.range.SearchPolicy states:

enum SearchPolicy: int;
    Policy used with the searching primitives lowerBound, upperBound, and
equalRange of SortedRange below.

    trot
        Searches with a step that is grows linearly (1, 2, 3,...) leading to a
quadratic search schedule (indexes tried are 0, 1, 3, 6, 10, 15, 21, 28,...)
Once the search overshoots its target, the remaining interval is searched using
binary search. The search is completed in ?(sqrt(n)) time. Use it when you are
reasonably confident that the value is around the beginning of the range.

    gallop
        Performs a galloping search algorithm, i.e. searches with a step that
doubles every time, (1, 2, 4, 8, ...) leading to an exponential search schedule
(indexes tried are 0, 1, 3, 7, 15, 31, 63,...) Once the search overshoots its
target, the remaining interval is searched using binary search. A value is
found in ?(log(n)) time.



But in the source code the enum contains a "linear" too:

/**
   Policy used with the searching primitives $(D lowerBound), $(D
   upperBound), and $(D equalRange) of $(LREF SortedRange) below.
 */
enum SearchPolicy
{
    /**
       Searches in a linear fashion.
    */
    linear,

    /**
       Searches with a step that is grows linearly (1, 2, 3,...)
       leading to a quadratic search schedule (indexes tried are 0, 1,
       3, 6, 10, 15, 21, 28,...) Once the search overshoots its target,
       the remaining interval is searched using binary search. The
       search is completed in $(BIGOH sqrt(n)) time. Use it when you
       are reasonably confident that the value is around the beginning
       of the range.
    */
    trot,

--