• d-bugmail puremagic.com (48/48) Sep 01 2010 http://d.puremagic.com/issues/show_bug.cgi?id=4787
• d-bugmail puremagic.com (10/10) Jan 09 2011 http://d.puremagic.com/issues/show_bug.cgi?id=4787
• d-bugmail puremagic.com (12/12) Mar 12 2013 http://d.puremagic.com/issues/show_bug.cgi?id=4787

d-bugmail puremagic.com writes:

http://d.puremagic.com/issues/show_bug.cgi?id=4787

           Summary: std.algorithm.bisectRight()
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: nobody puremagic.com
        ReportedBy: bearophile_hugs eml.cc



std.algorithm.findAmongSorted() is sometimes useful, but it doesn't cover all
usages. For example you may need to find the place where to insert a value
inside a sorted array of floating point values.

To this purpose it's useful a function similar to (a more generic version for
ranges may be written):


import std.stdio: writeln;

/**
Locate the proper insertion point for item in a sorted array to
maintain sorted order. If x is already present in arr, the
insertion point will be after (to the right of) any existing entries.
*/
int bisectRight(T)(T[] arr, T x) {
    int lo = 0;
    int hi = arr.length;
    while (lo < hi) {
        int mid = (lo + hi) / 2; // lo + hi may cause overflow!
        if (x < arr[mid])
            hi = mid;
        else
            lo = mid + 1;
    }
    return lo;
}

// demo ----------------
void main(string[] args) {
    auto array = [1.5, 3.2, 3.61, 11.0];
    assert(bisectRight(array, 0.0) == 0);
    assert(bisectRight(array, 4.1) == 3);
    assert(bisectRight(array, 50.5) == 4);
}


See also, for other quite useful ideas:
http://docs.python.org/library/bisect.html

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

d-bugmail puremagic.com writes:

http://d.puremagic.com/issues/show_bug.cgi?id=4787


Andrei Alexandrescu <andrei metalanguage.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
                 CC|                            |andrei metalanguage.com
         AssignedTo|nobody puremagic.com        |andrei metalanguage.com


-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

d-bugmail puremagic.com writes:

http://d.puremagic.com/issues/show_bug.cgi?id=4787


Andrei Alexandrescu <andrei erdani.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED



PDT ---
The SortedRange primitives lowerBound, upperBound, trisect etc. should cover
this. Please reopen if not.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------